Remove Duplicates from Sorted List II
Medium · Linked Lists · Linked List · Two Pointers
Problem
You are given the head of a linked list sorted in non-decreasing order. Delete every node whose value appears more than once, so that only the values that occur exactly once in the original list remain. Return the head of the result, which stays sorted.
Every copy of a repeated value goes, not just the extra ones: [1,2,2,3] becomes [1,3].
Examples
Input: head = [1,2,2,3,4,4,5] Output: [1,3,5]
Both 2s and both 4s go; 1, 3 and 5 appear once.
Input: head = [3,3,3] Output: []
3 is repeated, so nothing is left.
Input: head = [1,1,1,2,3] Output: [2,3]
The first three nodes go, so the result starts at 2.
Constraints
- The list has between 0 and 300 nodes.
- -100 <= Node.val <= 100
- The list is sorted in non-decreasing order.
Approaches
- Baseline: count every value, then rebuild — time O(n), space O(n)
Follow-up
The first version of this problem keeps one copy of each value instead of none; then prev is never needed, because the first node of a run always stays. If the list were not sorted, equal values would be scattered and you would need a count of every value first, as the second solution does. Both of those are use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
