82. Remove Duplicates from Sorted List II
mediumLike 83 but stricter — any value that appears more than once is removed entirely, not collapsed to a single occurrence. The dummy-head plus look-ahead pattern: you peek two nodes forward to decide whether to skip a whole run.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
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.
Constraints
The number of nodes in the list is in the range [0, 300].-100 <= Node.val <= 100The list is guaranteed to be sorted in ascending order.
Examples
Example 1
head = [1,2,3,3,4,4,5][1,2,5]Example 2
head = [1,1,1,2,3][2,3]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Unlike the easy version, the head itself may need to go — use a dummy node.
Hint 2
Stand at prev = dummy. Peek at prev.next and prev.next.next. If their values match, skip every subsequent node sharing that value, then rewire prev.next to skip the whole run.
Hint 3
Only advance prev when prev.next is a confirmed-unique node. Otherwise prev stays put while you keep skipping.
Solution approach
Reveal approach
Dummy-head with look-ahead skip. Allocate a dummy with dummy.next = head and let prev = dummy. Loop while prev.next is non-null: if prev.next.next exists and prev.next.val == prev.next.next.val, capture dupVal = prev.next.val and run an inner loop that advances prev.next while prev.next and prev.next.val == dupVal — this excises the entire run by reassigning prev.next past every duplicate, including the one that was prev.next itself. Otherwise, advance prev = prev.next. Return dummy.next. The key invariant: prev always points at the last confirmed-unique node, never inside a duplicate run. O(n) time, O(1) extra space.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- linked-list
- dummy-head
- pointer-rewiring
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Bloomberg
More Linked Lists practice problems
- 2. Add Two Numbers
- 19. Remove Nth Node From End of List
- 21. Merge Two Sorted Lists
- 24. Swap Nodes in Pairs
- 25. Reverse Nodes in k-Group
- 61. Rotate List
- 83. Remove Duplicates from Sorted List
- 86. Partition List