DSA problem
Remove Duplicates from Sorted List II
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 still sorted.
This is the stricter sibling of the basic duplicate-removal problem. There you keep one copy of every value; here you must remove a value entirely if it appears more than once. A run of three nodes with value 2 disappears completely rather than collapsing to a single node.
The complication is that the head itself may be a duplicate that must be deleted. To handle that uniformly, prepend a dummy node before the head and track a prev pointer that always references the last confirmed-distinct node, initially the dummy.
The optimal approach makes a single pass. A current pointer scans forward; whenever current.val equals current.next.val, advance current past the entire run of equal values, then link prev.next directly to the node after that run, skipping every duplicate. If current has no equal neighbor, it is unique, so move prev forward to it. Returning dummy.next yields a list of values that each appeared exactly once, all in O(n) time and O(1) space.
Examples
head = [1,2,3,3,4,4,5][1,2,5]head = [1,1,1,2,3][2,3]head = [1,1][]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 non-decreasing order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.