Remove Duplicates from Sorted List II — Delete All Occurrences with Dummy Head

Problem Statement#

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Constraints:

• The number of nodes in the list is in the range [0, 300]
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order

Example 1:

Input:  head = [1, 2, 3, 3, 4, 4, 5]
Output: [1, 2, 5]
Explanation: All nodes with values 3 and 4 (which appeared more than once) are removed.

Example 2:

Input:  head = [1, 1, 1, 2, 3]
Output: [2, 3]
Explanation: All nodes with value 1 are removed.

Example 3:

Input:  head = [1, 1]
Output: []

Why This Problem Matters#

Remove Duplicates from Sorted List II (LeetCode 82) is the harder sibling of LC 83. The difference: LC 83 keeps one copy of each duplicate value; LC 82 removes all copies. This distinction changes the algorithm fundamentally. In LC 83, when you find a duplicate, you skip one node. In LC 82, when you find any duplicate, you must skip all nodes with that value and not keep any.

Google, Amazon, and Bloomberg ask this problem in interviews because it tests the predecessor-skip pattern with a more complex skip condition. You need a dummy head (because the head itself might be deleted), a predecessor pointer prev, and a two-level while loop: one to advance prev, and one nested inside to skip all duplicates of a given value.

The problem also illustrates an important interview skill: recognizing when you cannot advance the predecessor pointer. In LC 83, prev always advances. In LC 82, prev only advances if the current node is unique — it stays put while you skip all duplicates.

The Core Insight#

Use a dummy head node before the real head. Keep prev pointing to the last confirmed unique node (or the dummy initially). Inspect prev.next:

• If prev.next and prev.next.next have the same value, it's a duplicate group. Record the duplicate value and skip all nodes with that value by walking curr through them, then set prev.next = curr (the first node after the duplicate group).
• If prev.next.next doesn't exist or has a different value, prev.next is a unique node — advance prev = prev.next.

Repeat until prev.next is None.

Visual Dry Run#

Input: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

Setup: dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5, prev = dummy

Return dummy.next = 1 -> 2 -> 5. Correct.

Head-deletion case: 1 -> 1 -> 2

Return dummy.next = 2. Correct — head was deleted.

Solution (Optimal)#

Python#

def deleteDuplicates(head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy  # last confirmed unique node (or dummy)
 
    while prev.next:
        curr = prev.next
        # Check if curr starts a duplicate group
        if curr.next and curr.val == curr.next.val:
            # Skip all nodes with this duplicate value
            dup_val = curr.val
            while curr and curr.val == dup_val:
                curr = curr.next
            prev.next = curr  # skip entire duplicate group
            # Do NOT advance prev — the new prev.next might also be a duplicate
        else:
            prev = prev.next  # curr is unique, advance prev
 
    return dummy.next

Time complexity: O(n) — each node is visited at most twice (once by curr, once when prev passes through).

Space complexity: O(1) — dummy node and two pointer variables.

JavaScript#

var deleteDuplicates = function(head) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
 
    while (prev.next !== null) {
        const curr = prev.next;
        if (curr.next !== null && curr.val === curr.next.val) {
            const dupVal = curr.val;
            let c = curr;
            while (c !== null && c.val === dupVal) {
                c = c.next;
            }
            prev.next = c;  // skip all duplicates
        } else {
            prev = prev.next;  // unique node, advance
        }
    }
 
    return dummy.next;
};

Complexity:

Common Mistakes#

1. Confusing LC 83 (keep one) with LC 82 (remove all). LC 83: when curr.val == curr.next.val, skip curr.next only. Keep curr. LC 82: when curr.val == curr.next.val, skip ALL nodes with that value including curr itself.

2. Advancing prev after a skip. After skipping a duplicate group and setting prev.next = curr, do NOT advance prev. The new prev.next might be another duplicate group (e.g., 1->1->2->2->3). Staying at prev allows the next iteration to check again.

3. Not using a dummy head. If the first node is part of a duplicate group (e.g., [1, 1, 2]), the head changes. Without a dummy, you need special logic to find the new head. The dummy makes prev the predecessor of every node, including the first one.

4. Using prev.next and prev.next.next without null checks. The while prev.next outer condition ensures prev.next exists. But inside, you must check curr.next (= prev.next.next) before accessing curr.next.val. The if curr.next and curr.val == curr.next.val condition handles this.

5. Using a sentinel value for dup_val instead of recording it. After the inner while loop, curr has moved past all duplicates. You need curr to know where to reconnect. Don't try to use curr.val at the end — curr is already past the duplicates.

Interview Tips#

1. State the key difference from LC 83: "In LC 83, when I find a duplicate, I skip the extra copy. In LC 82, I skip the entire duplicate group — even the first occurrence."

2. Explain why prev doesn't advance after a skip: "After skipping, the new prev.next could be another duplicate group. I need to check again before advancing prev."

3. Walk the head-deletion case: [1, 1, 2] — show that the dummy handles it: prev stays at dummy, skips both 1s, advances to 2.

4. Use the inner while loop explicitly: Show that you skip all nodes with dup_val, not just one. This handles triples and longer runs.

5. Test [1, 1]: After skipping, prev.next = None. Return dummy.next = None. Empty list. Correct.

Follow-up Questions#

Q: What's the difference between LC 83 and LC 82 in code? LC 83 uses if curr.val == curr.next.val: curr.next = curr.next.next (skip one copy). LC 82 uses an inner while loop to skip all copies and requires a predecessor pointer that doesn't advance after a skip.

Q: What if the list is not sorted? With an unsorted list, duplicates aren't consecutive. You'd need a hash set: two passes — first pass records all values that appear more than once, second pass removes nodes with those values. O(n) time and O(n) space.

Q: Can you do it recursively? Yes: deleteDuplicates(head). If head and head.next have the same value, skip all with that value and recurse: return deleteDuplicates(non_dup_head). If unique: head.next = deleteDuplicates(head.next); return head. O(n) stack space.

Q: What if values can be negative? The algorithm doesn't assume positive values — it compares values for equality. Negative values work correctly.

Q: Can you solve it in one line with Python list comprehension? Not directly on a linked list, but you could collect values, filter for non-duplicates, and rebuild. That's O(n) time and O(n) space — less efficient and defeats the purpose of practicing linked list manipulation.

Key Takeaways#

• Use a dummy head — the original head might be deleted.
• prev is the last confirmed unique predecessor. It only advances when the current node is confirmed unique.
• When a duplicate is found, use an inner while loop to skip ALL nodes with that value — not just one.
• Do NOT advance prev after a skip — the new prev.next might also need skipping.
• This is the harder sibling of LC 83 — the key difference is "remove all" vs "keep one."
• Time O(n), Space O(1) — single pass with a predecessor pointer and inner skip loop.