Coding Interview PatternsRemove Duplicates from Sorted List II
MediumFast and Slow Pointers
Remove Duplicates from Sorted List II
Explanation & Solution
Description
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.
Input:head = [1,2,3,3,4,4,5]
0
1
1
2
2
3
3
3
4
4
5
4
6
5
Output:[1,2,5]
0
1
1
2
2
5
Explanation: Nodes with values 3 and 4 appear more than once, so all their occurrences are removed.
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
Approach
Fast and Slow Pointers pattern
1. Create a Dummy Head
- Create a dummy node that points to
head. - This handles the edge case where the head itself needs to be removed (e.g.,
[1,1,2]). - Set
prev = dummyandcurr = head.
2. Traverse the List
- Walk through the list with
curr. - At each step, check if
curr.val === curr.next.val(i.e., duplicates exist).
3. Skip All Duplicates
- If a duplicate is found, save the duplicate value.
- Advance
currpast all nodes with that value. - Update
prev.next = currto bypass the entire group of duplicates. - Note:
prevdoes not move forward — it stays in place because the next node might also be a duplicate.
4. Advance on Unique Nodes
- If
curris unique (no duplicate), simply move bothprevandcurrforward by one step.
5. Return the Result
- The modified list starts at
dummy.next. - Convert the remaining linked list to an array and return it.
Key Insight
- The dummy node is essential — without it, removing duplicates at the head of the list requires special-case logic.
- The
prevpointer always points to the last confirmed unique node, allowing us to "skip over" entire groups of duplicates.
Time
O(n)each node is visited at most twice.Space
O(1)only pointer variables are used (excluding the output array).Visualization
Input:
Linked List Traversal
—
Press play to start traversal
Slow (S)Fast (F)Both
8 steps