Remove Duplicates from Sorted List II — Solution

Problem

Given a sorted linked list, remove every node whose value appears more than once — not just the extra copies, but all copies. The remaining nodes should stay in sorted order.

[1,2,3,3,4,4,5]

• Input: head = [1, 2, 3, 3, 4, 4, 5]
• Output: [1, 2, 5]
• Explanation: Both 3 and 4 appear more than once, so all of their nodes are removed.

Counter-example to clarify the distinction from the simpler variant: [1, 1, 2] → [2], not [1, 2]. Every copy of 1 is eliminated, not just the extra one.

Intuition

Because the list is sorted, all duplicates of any value are consecutive. We can scan with a pointer and, whenever we see two adjacent nodes with equal values, advance past every node with that value before relinking. A dummy node placed before the head eliminates the special case where the head itself is a duplicate.

Solution — Sentinel + Two Pointers

Attach a dummy node before the head so prev always has a predecessor to relink through. When curr starts a run of equal values, skip the entire run by advancing curr past every node with that value, then bridge prev directly to the node after the run.

1. Create a dummy node and set dummy.next = head. Set prev = dummy, curr = head.
2. While curr is not None:
   • If curr.next exists and curr.val == curr.next.val, record dup_val and advance curr forward until curr.val != dup_val. Then set prev.next = curr to skip all duplicates without moving prev.
   • Otherwise, advance prev = curr.
   • Advance curr = curr.next.
3. Return dummy.next.

1class Solution:
2    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        dummy = ListNode(0)
4        dummy.next = head
5        prev = dummy
6        curr = head
7
8        while curr:
9            if curr.next and curr.val == curr.next.val:
10                dup_val = curr.val
11                # Advance past every node that carries this duplicate value
12                while curr and curr.val == dup_val:
13                    curr = curr.next
14                # Bridge prev over all the removed nodes
15                prev.next = curr
16            else:
17                prev = curr
18                curr = curr.next
19
20        return dummy.next

Time: O(n) — every node is visited exactly once. Space: O(1) — only a constant number of pointers, no auxiliary data structures.

Complexity Summary

Common Mistakes

• Omitting the dummy node: Without it, the head itself requires special-case logic when it participates in a duplicate sequence. The sentinel node lets prev always have a valid predecessor to relink.
• Moving prev after skipping duplicates: After bridging prev.next = curr, prev must stay put — it already points past all the removed nodes. Advancing prev as if the skip hadn't happened leaves dangling references.
• Stopping the skip loop one node too early: The inner loop must leave curr pointing at the first node whose value differs from dup_val, not at the last duplicate. Stopping on the final duplicate node leaves one stray copy in the list.
• Confusing this with LeetCode 83 (Remove Duplicates I): In that problem one copy of each repeated value is kept. Here every copy is deleted. If [1, 1, 2] produces [1, 2] instead of [2], the wrong variant was implemented.
• Not handling an all-duplicate list: Input [1, 1, 1] should produce an empty list. The dummy-node approach handles this naturally — prev.next ends up as None and dummy.next correctly returns None.

Related Problems

• remove-duplicates-from-sorted-list — the simpler variant that retains one copy of each repeated value rather than removing all copies
• partition-list — rearranging linked list nodes around a pivot using the same sentinel + two-pointer technique
• odd-even-linked-list — splitting a list into two interleaved groups by advancing two running pointers simultaneously
• merge-two-sorted-lists — another sorted linked list problem requiring careful pointer advancement without losing nodes
• delete-node-in-a-bst — deletion in a sorted structure where surrounding nodes must be relinked after removal