Remove Duplicates from Sorted List II
Problem
head of a linked list sorted in ascending order.
Delete every node whose value appears more than once — not just the extra
copies, all of them — so only values that occurred exactly once remain. Return the
resulting list, still sorted.[1,2,3,3,4,4,5]Output[1,2,5][1,1,1,2,3]Output[2,3][2,2]Output[]0 ≤ n ≤ 300 · -100 ≤ Node.val ≤ 100 · list is sorted ascending
Try it yourself
class Solution {
public ListNode deleteDuplicates(ListNode head) {
}
}
prev to the last node known to be unique (starting at a dummy) and,
whenever a run of length ≥ 2 starts, jump past the whole run and link
prev to whatever follows.Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.
Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.
Open the Linked List Techniques guide →Approaches
Brute ForceCount Frequencies, Keep Singletons
O(n)Space O(n)First pass: count how often each value occurs in a hash map. Second pass: append to a new chain only nodes whose count is exactly 1. This ignores the sorted order entirely, so it would even work on unsorted input.
public ListNode deleteDuplicates(ListNode head) { Map<Integer, Integer> count = new HashMap<>(); for (ListNode c = head; c != null; c = c.next) count.merge(c.val, 1, Integer::sum); ListNode dummy = new ListNode(0), tail = dummy; for (ListNode c = head; c != null; c = c.next) { if (count.get(c.val) == 1) { tail.next = c; tail = c; } } tail.next = null; // cut off any trailing duplicates return dummy.next; }
Straightforward, but the map costs O(n) memory that sortedness makes unnecessary.
BetterRecursion on the Remaining List
O(n)Space O(n)Look only at the head. If it differs from the next node it is unique: keep it and recurse on the rest. If it equals the next node, skip the entire run of that value and return the answer for whatever follows the run.
public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; if (head.val != head.next.val) { head.next = deleteDuplicates(head.next); return head; } int dup = head.val; while (head != null && head.val == dup) head = head.next; // drop the whole run return deleteDuplicates(head); }
No hash map and very readable, but uses up to n stack frames.
OptimalDummy Head + Iterative Run Skipping
O(n)Space O(1)A dummy before the head means the real head can be deleted like any other
node. prev always points at the last confirmed-unique node. If
cur starts a run, advance cur past it and set
prev.next = cur; otherwise cur is unique, so
prev moves onto it.
public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(0, head); ListNode prev = dummy, cur = head; while (cur != null) { if (cur.next != null && cur.next.val == cur.val) { int dup = cur.val; while (cur != null && cur.val == dup) cur = cur.next; prev.next = cur; // unlink the entire run } else { prev = cur; // cur is unique, keep it cur = cur.next; } } return dummy.next; }
One pass, constant memory, no special case for the head.
prev after removing a run — the next
node might start another run.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Count Frequencies, Keep Singletons | O(n) | O(n) |
| Better | Recursion on the Remaining List | O(n) | O(n) |
| Optimal | Dummy Head + Iterative Run Skipping | O(n) | O(1) |
- Keeping one copy of a duplicated value (that is problem 83, not this one).
- Advancing
prevright after deleting a run — misses back-to-back runs like[1,1,2,2]. - Special-casing the head instead of using a dummy — easy to get wrong when the head is duplicated.
- Contrast with Remove Duplicates I (83) to show you read the statement carefully.
- Use the sortedness: duplicates are adjacent, so no map is needed.
- Test aloud: all duplicates, duplicates at head, duplicates at tail, no duplicates.