Remove Duplicates from Sorted List II

Medium#82dummy head

You get a sorted linked list. Delete every value that appears more than once, all of its copies, and keep only the values that appear exactly once. Return the head. Our example: 2 → 2 → 5 → 7 → 7 → 9 — the answer is 5 → 9.

82 Remove Duplicates from Sorted List IIWalkthrough · 1×

Example: 2 → 2 → 5 → 7 → 7 → 9: 2 and 7 repeat, 5 and 9 do not.

nonedummy225779
not checked yetcurcur.next, compared / a copy of dupkept, up to prevcut out

A dummy node in front of the head: if the head itself repeats, there is still a node before it to relink

01/33
restart · back · play · step
Speed
1function deleteDuplicates(head):
2 dummy = new node whose next is head
3 prev = dummy
4 cur = head
5 while cur is not none:
6 if cur.next is none or cur.next.val != cur.val:
7 prev = cur
8 cur = cur.next
9 else:
10 dup = cur.val
11 while cur is not none and cur.val == dup:
12 cur = cur.next
13 prev.next = cur
14 return dummy.next
state
prev
–
cur
–
dup
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The list is sorted, so the copies of a value stand side by side: one look at cur.next tells whether cur repeats, and cur then walks past every copy of dup.
  2. prev only moves onto a node known to have no copy, so prev.next = cur cuts out all the copies with one link, the first one included.
  3. The dummy is a node before the head that can never be deleted. Here the head 2 repeats, and dummy.next simply becomes 5.

Complexity

Time O(n): cur only moves forward, one step per node. Memory O(1): two pointers and the dummy.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.