Remove Duplicates from Sorted List II
Remove Duplicates from Sorted List II: delete every node that has a duplicate value, keeping only values that appear exactly once in the sorted list.
- The number of nodes in the list is in the range [0, 300]
- -100 <= Node.val <= 100
- The list is sorted in ascending order
Intuition
This deletes all copies of a repeated value, not just the extras — so a node can only be kept after confirming its successor differs. Because the list is sorted, duplicates are contiguous, and a single pass can detect a run and skip it entirely. The head itself may be deleted, which is what makes a dummy node in front of the list the natural way to avoid special-casing.
A dummy head is the standard answer whenever the first node might be removed or replaced, because it makes the head an ordinary case. Combined with a trailing pointer it handles Remove Nth Node From End and Partition List the same way.
Approach
Before reading on: work out why a node cannot be kept until its successor has been inspected, and what that implies about where your pointer must sit. Then check what your code does when the very first value is duplicated.
Deleting every copy, not just the repeats
The easier sibling problem keeps one node from each run. This one deletes the entire run: [1,2,2,3] becomes [1,3], not [1,2,3]. The consequence is that no node can be kept on sight — you must first look at what follows it. So the pointer that decides survival has to sit before the candidate, comparing prev.next.val against the value after it, which is why the traversal is structured around a trailing pointer rather than a single cursor.
The dummy node removes the head special case
If the first value is duplicated, the head itself disappears, and the caller's reference must end up pointing somewhere else. Allocating dummy = ListNode(0, head) and returning dummy.next at the end means the code never needs to ask whether it is deleting the head — the dummy always has a valid predecessor role. Without it every deletion needs a branch checking whether prev exists, and that branch is where most incorrect solutions fail on inputs like [1,1,2].
Skipping a whole run in one move
Walk with prev (trailing, known-good) and curr (scanning). When curr.next exists and holds the same value, advance curr until it reaches the last node of the run, then set prev.next = curr.next to splice out every node in it at once. When curr.next differs, the value is unique, so prev advances to curr. Either way curr then moves forward. Each node is examined a constant number of times, giving O(n) time with O(1) extra space — the dummy is a single node, not proportional to the input.
Solution & live demo
Common pitfalls
Keeping one copy of each duplicate
if curr.next and curr.next.val == curr.val:
curr.next = curr.next.nextskip the entire run, then prev.next = curr.next
That is the solution to the easier variant, which keeps one node per run. Here every node with a repeated value must go, so [1,2,2,3] must become [1,3] rather than [1,2,3].
Omitting the dummy node
prev = head curr = head
dummy = ListNode(0, head) prev = dummy
When the head itself is part of a duplicate run there is no predecessor to splice from, so the deletion cannot be expressed and the returned head still points at a removed node.
Advancing prev after splicing out a run
prev.next = curr.next prev = curr
prev.next = curr.next # prev stays put
curr is the last node of a deleted run, so moving prev onto it re-attaches the very nodes just removed. prev must remain on the last surviving node.
Edge cases
curr is None immediately and the dummy's next is still None.
The entire list is one run and is removed, returning an empty list.
The dummy lets the head be spliced out without a special branch.
The run ends at the tail, so prev.next becomes None.
prev advances every step and the list is returned unchanged.