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”