Purge Duplicated Values
MediumLinked List
Problem
A ballot list is sorted in non-decreasing order of candidate id. Any candidate who appears more than once is disqualified entirely.
Given the head of the sorted list, remove every node whose value occurs more than once, keeping only values that appear exactly once, and return the head.
Example 1
- Input:
- head = [1, 2, 3, 3, 4, 4, 5]
- Output:
- [1, 2, 5]
3 and 4 each appear twice, so all their nodes go.
Example 2
- Input:
- head = [1, 1, 1, 2, 3]
- Output:
- [2, 3]
The head itself is disqualified.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -10^4 ≤ node.val ≤ 10^4
- The list is sorted in non-decreasing order.
Hint
Show the first hint
Unlike keeping one copy, here even the first copy must go, so you cannot decide while standing on it alone.
Walkthrough
How to approach it
01Clarify before coding
- Keep one copy of duplicates, or drop them all? Drop them all.
- Is the input sorted? Yes, so copies are adjacent.
- Can the head be removed? Yes, so use a dummy node.
02Brute force
Count every value in a hash map in one pass, then rebuild the list from values with count 1.
Cost: O(n) time but O(n) extra space; the sortedness makes the map unnecessary.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.