2.1 Remove Dups: Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
we simply iterate through the linked list, adding each element to a hash table. When we discover a duplicate element, we remove the element and continue iterating. We can do this all in one
pass since we are using a linked list.
public void deleteDups(LinkedListNode n) {
HashSet<Integer> set = new HashSet<Integer>();
LinkedListNode previous = null;
while (n != null) {
if (set.contains(n.data)) {
previous.next = n.next;
} else {
set.add(n.data);
previous = n;
}
n = n.next;
}
}
The above solution takes 0 (N) time, where N is the number of elements in the linked list.
Follow Up: No Buffer Allowed
If we don't have a buffer, we can iterate with two pointers: current which iterates through the linked list, and runner which checks all subsequent nodes for duplicates.
public void deleteDups(LinkedListNode n){
LinkedListNode current = n;
while(current!=null){
//Remove all future nodes that have the same value
LinkedListNode runner = current;
while(runner.next !=null){
if(runner.next.data==current.data){
runner.next = runner.next.next;
}else{
runner = runner.next;
}
}
current = current.next;
}
This code runs in O( 1) space, but O(N2) time.
