Remove Duplicates from Sorted List II

The key idea

Use a dummy head so the real first node can be deleted uniformly. Keep a prev pointer at the last node known to be unique, and a curr scanner. When curr starts a run of equal values, skip the entire run before relinking prev.next — a node from a duplicate run is never kept.

Problem

You are given the head of a sorted linked list. Delete all nodes that have duplicate numbers, leaving only numbers that appear exactly once in the original list. Return the linked list sorted as well.

Note the difference from the simpler variant: you do not merely collapse a run down to a single copy. If a value appears more than once, every node carrying that value is removed. A node survives only when its value is distinct across the whole list.

Because the list is already sorted in ascending order, all nodes sharing a value are adjacent, which lets you detect and delete a duplicate run in a single forward pass. A dummy head node placed before head lets you delete the original first node without a special case.

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.

Examples

Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]

Input: head = [1,1,1,2,3] Output: [2,3]

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →