Remove duplicates
Write code to remove duplicates from an unsorted linked list. Could you also solved this without using a temporary buffer?
Link here to the repo to solve the problem
👉👌 Tips
Have you tried a hash table? You should be able to do this in a single pass of the linked list.
Without extra space, you’ll need a (N2) time. Try using two pointers, where the second one searches ahead of the first one.
👊 Solution 1
I wrote a fairly easy solution in which we add every unique node data onto a HashSet, every time we see that it already exists in this set we just skip to the next node - hence removing the duplicate. Note that at the very end we have to also do it for the very last node in the List:
public static void removeDupplicates(SingleLinkedListNode head) {
SingleLinkedListNode n = head;
HashSet<Integer> a = new HashSet<>();
while (n.next != null) {
int i = n.data;
if (!a.contains(i)) a.add(i);
if(a.contains(n.next.data) && n.next.next != null) {
n.next = n.next.next;
}
if(a.contains(n.next.data)) {
n.next = null;
} else {
n = n.next;
}
}
}
Question borrowed from “Cracking the coding interview”