Given a linked list sorted in ascending order, remove the duplicates so each value appears once. Return the head.
undupe(head)
Input format: space-separated sorted node values. Output the de-duplicated list.
1 → 1 → 2 → 3 → 3 // → 1 → 2 → 3
1 → 1 → 1 // → 1
(empty) // → (empty)
The list is sorted, and that fact does most of the work: if a value repeats, every copy sits right next to every other copy — no way for a duplicate to land far from its twin. You never need to search the whole list, only compare a node to its immediate neighbor.
Walk with one pointer from the head. At each node, look at the next node. If the values match, splice the next node out by pointing the current node's next past it — the duplicate is gone. If they differ, advance the pointer and repeat.
The easy mistake: what to do right after removing a duplicate. A run like 2 2 2 needs the current node to stay put and re-check the new next node, since removing one copy still leaves it next to another copy of the same value. Only advance when the comparison shows the values genuinely differ — that's what collapses a run of any length to one value.
Sortedness guarantees duplicates are adjacent, so one forward pass suffices — no backtracking, no searching elsewhere. O(n) time, and since you're only rewiring existing next pointers rather than allocating anything, O(1) extra space. A precondition on the input (sortedness) turns an all-pairs comparison problem into a neighbors-only one.
def undupe(head):
node = head
while node is not None and node.next is not None:
if node.val == node.next.val:
node.next = node.next.next
else:
node = node.next
return head
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.