DDSA Solutions

Remove all occurences of duplicates in a linked list

Time: O(n)
Space: O(n)
Advertisement

Intuition

Remove all nodes that have duplicate values in a linked list.

Algorithm

  1. 1Frequency map: count occurrences. Rebuild list keeping only nodes with count == 1. Or dummy head + skip runs.

Common Pitfalls

  • Same as LC 82. Use dummy head. Skip entire runs of same value. O(n).
Remove all occurences of duplicates in a linked list.java
Java
// Approach: HashMap to count frequencies. Rebuild list keeping only nodes with frequency 1.
// Time: O(n) Space: O(n)

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {
    public Node removeAllDuplicates(Node head) {
        Node curr = head;
        Node dummy = new Node(-1);
        Node newCurr = dummy;

        while (curr != null) {
            int d = curr.data;
            if ((curr.next != null && d != curr.next.data) || curr.next == null) {
                newCurr.next = new Node(d);
                newCurr = newCurr.next;
                curr = curr.next;
            } else {
                while (curr != null && d == curr.data)
                    curr = curr.next;
            }
        }

        return dummy.next;
    }
}
Advertisement
Was this solution helpful?