Remove duplicates from sorted DLL
HardSkip runs of equal values
Problem
Given the head of a sorted doubly linked list, remove nodes with duplicate values so each value appears once. Return the head.
Since it's sorted, skip any node equal to the one before it as you walk the list.
The idea
Sorted order puts duplicates next to each other, so for each node advance past every following node with the same value and relink. Only adjacent comparisons are needed.
The trick
- Relink both next and prev after skipping a run.
- Do not advance the outer pointer while it is still equal to its successor.
- One pass, O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — head = [1, 1, 2, 3, 3] Values: 1, 1, 2, 3, 3.
1cur = head2while cur and cur.next:3 if cur.val == cur.next.val:4 cur.next = cur.next.next5 if cur.next: cur.next.prev = cur6 else: cur = cur.next7return headInput
- array
- [1, 1, 2, 3, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 1 -> 2 -> 3 -> 3
- Output:
- 1 -> 2 -> 3
- Explanation:
- Adjacent duplicates collapse to one.
Example 2
- Input:
- list = 1 -> 1 -> 1
- Output:
- 1
- Explanation:
- All the same → just [1].
Example 3
- Input:
- list = 1 -> 2 -> 3
- Output:
- 1 -> 2 -> 3
- Explanation:
- Nothing to remove.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.