Problem Description

You are given the head of a sorted linked list that may contain duplicate values. Your task is to delete all nodes that have duplicate numbers, removing both the duplicates and the original occurrence. Only nodes with distinct (unique) values should remain in the final linked list.

The resulting linked list should still be sorted.

For example:

• If the input linked list is 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5, the output should be 1 -> 2 -> 5 (both 3 and 4 appear multiple times, so all occurrences are removed)
• If the input linked list is 1 -> 1 -> 1 -> 2 -> 3, the output should be 2 -> 3 (the value 1 appears multiple times, so all occurrences are removed)

The key point is that if a value appears more than once in the linked list, you need to remove all nodes with that value, not just the duplicates.

Intuition

Since we need to remove all nodes with duplicate values (including the original), we face a challenge: how do we know if a node should be kept or removed? We need to look ahead to see if the current node's value appears again.

The key insight is to use two pointers: one (pre) that stays at the last valid node we want to keep, and another (cur) that explores ahead to find duplicates.

When we encounter a node, we need to check if it has duplicates by looking at subsequent nodes. If cur.val == cur.next.val, we know this value appears multiple times, so we need to skip all nodes with this value. We keep moving cur forward as long as we see the same value.

After skipping all duplicates of a value, we need to determine if any duplicates were actually found. This is where the condition pre.next == cur becomes crucial:

• If pre.next == cur, it means cur didn't move forward (no duplicates were found), so this node should be kept. We move pre to cur.
• If pre.next != cur, it means cur moved forward (duplicates were found), so we need to skip all these duplicate nodes by setting pre.next = cur.next.

We use a dummy head node to handle the edge case where the first few nodes of the original list need to be removed. Without the dummy node, we'd have to write special logic to update the head pointer when removing nodes from the beginning.

This approach allows us to remove all duplicate nodes in a single pass through the linked list, maintaining the sorted order naturally since we're only removing nodes, not rearranging them.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

We implement a single-pass solution using two pointers to track and remove all nodes with duplicate values.

Step 1: Setup dummy node and pointers

• Create a dummy head node dummy and set dummy.next = head to handle edge cases where the first nodes need to be removed
• Initialize pointer pre pointing to dummy (tracks the last valid node to keep)
• Initialize pointer cur pointing to head (explores the list to find duplicates)

Step 2: Traverse the linked list While cur is not null:

1. Find all duplicates of current value

   • While cur.next exists and cur.next.val == cur.val:
     • Move cur forward: cur = cur.next
   • This loop positions cur at the last node of a sequence of duplicate values

2. Determine if duplicates were found

   • Check if pre.next == cur:
     • If true: No duplicates were found (cur didn't move), so this node should be kept
       • Move pre forward: pre = cur
     • If false: Duplicates were found (cur moved forward), so skip all these nodes
       • Connect pre to the node after all duplicates: pre.next = cur.next

3. Move to next node

   • Move cur forward: cur = cur.next

Step 3: Return result

• Return dummy.next as the new head of the modified linked list

Example walkthrough: For linked list 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5:

• Start: pre at dummy, cur at 1
• Node 1: No duplicates, pre moves to 1
• Node 2: No duplicates, pre moves to 2
• Node 3: Found duplicate (next is also 3), cur moves to second 3, then pre.next = cur.next (connects 2 to 4)
• Node 4: Found duplicate (next is also 4), cur moves to second 4, then pre.next = cur.next (connects 2 to 5)
• Node 5: No duplicates, pre moves to 5
• Result: 1 -> 2 -> 5

The time complexity is O(n) where n is the number of nodes, and space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with the linked list: 1 -> 1 -> 2 -> 3 -> 3

Initial Setup:

• Create dummy node pointing to head: dummy -> 1 -> 1 -> 2 -> 3 -> 3
• pre points to dummy
• cur points to first 1

Iteration 1: (cur at first 1)

• Check for duplicates: cur.next.val (1) == cur.val (1) ✓
• Move cur forward to second 1
• Now cur is at the last 1 in the sequence
• Check if duplicates found: pre.next (first 1) != cur (second 1) → duplicates found!
• Skip all 1s: pre.next = cur.next (dummy now points to 2)
• Move cur to 2
• State: dummy -> 2 -> 3 -> 3, pre at dummy, cur at 2

Iteration 2: (cur at 2)

• Check for duplicates: cur.next.val (3) != cur.val (2) ✗
• No duplicates found: pre.next (2) == cur (2) ✓
• Keep this node: pre = cur (pre moves to 2)
• Move cur to first 3
• State: dummy -> 2 -> 3 -> 3, pre at 2, cur at first 3

Iteration 3: (cur at first 3)

• Check for duplicates: cur.next.val (3) == cur.val (3) ✓
• Move cur forward to second 3
• Now cur is at the last 3 in the sequence
• Check if duplicates found: pre.next (first 3) != cur (second 3) → duplicates found!
• Skip all 3s: pre.next = cur.next (2 now points to null)
• Move cur to null
• State: dummy -> 2, pre at 2, cur at null

Final Result: Return dummy.next which gives us: 2

The linked list 1 -> 1 -> 2 -> 3 -> 3 becomes just 2 after removing all nodes with duplicate values.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list.

The algorithm uses a single pass through the linked list. The outer while loop iterates through each unique position in the list, and the inner while loop skips over duplicate nodes. Even though there are nested loops, each node is visited at most twice (once by the outer loop's cur pointer and potentially once by the inner loop when checking for duplicates). Therefore, the total number of operations is proportional to the number of nodes in the list, resulting in linear time complexity.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space. It creates a few pointer variables (dummy, pre, and cur) to traverse and modify the linked list in-place. No additional data structures that grow with the input size are used. The space usage remains constant regardless of the length of the input linked list.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly handling consecutive groups of duplicates

The Problem: A common mistake is not properly resetting the pointers when dealing with consecutive groups of duplicates. For example, with input 1 -> 2 -> 2 -> 3 -> 3 -> 4, after removing the 2s, if the logic doesn't correctly position the pointers, it might fail to detect the 3s as duplicates.

Why it happens: After removing a group of duplicates by setting prev.next = curr.next, the curr pointer moves to curr.next. If we immediately move prev forward without checking if this new position also contains duplicates, we'll miss them.

The Solution: The provided code correctly handles this by NOT moving prev forward when duplicates are found. The key is the conditional check:

if prev.next == curr:
    prev = curr  # Only move prev if no duplicates were found
else:
    prev.next = curr.next  # Skip duplicates, but keep prev in place

This ensures prev stays at the last valid node until we find a non-duplicate value.

Pitfall 2: Forgetting to use a dummy node

The Problem: Without a dummy node, handling cases where the first element(s) need to be removed becomes complex. For input like 1 -> 1 -> 2 -> 3, we need to remove all 1s and return 2 as the new head.

Why it happens: Direct manipulation of the head pointer requires special case handling:

• Need to track when the head itself changes
• Must update the head reference multiple times if initial elements are duplicates
• Edge case when all elements are duplicates (should return None)

The Solution: Always use a dummy node that points to the original head:

dummy = ListNode(next=head)
prev = dummy

This provides a stable reference point and eliminates special cases. The actual head of the result is always dummy.next, regardless of what nodes were removed.

Pitfall 3: Off-by-one error in duplicate detection

The Problem: Using the wrong comparison logic like checking curr.val == prev.val instead of curr.next.val == curr.val can lead to incorrect duplicate detection.

Why it happens: Confusion about which nodes to compare - should we look backward or forward? Looking backward would require keeping track of previous values and makes the logic more complex.

The Solution: Always look forward to detect duplicates:

while curr.next and curr.next.val == curr.val:
    curr = curr.next

This approach naturally groups all nodes with the same value together and positions curr at the last node of any duplicate sequence, making it easy to skip the entire group if needed.