331. Purge Repeated Values
A librarian keeps a sorted chain of catalogue numbers: each node stores one number and a link to the next, the numbers never decrease, and head is the first node. Some numbers were entered several times by mistake, and the librarian decides that any number appearing more than once is unreliable and must vanish completely.
Delete every node whose value occurs two or more times in the chain, so that not even one copy of such a value remains, and return the head of what is left. Numbers that appear exactly once keep their nodes and their order. If everything is removed, return an empty chain. Because the chain is sorted, equal values sit next to each other, and one pass with a few pointers is enough.
Example 1
- Input:
- head = [2,2,5,7,7,7,9,12,12]
- Output:
- [5,9]
- Explanation:
The values 2, 7 and 12 repeat and are removed entirely, leaving 5, 9.
Example 2
- Input:
- head = [-4,-1,-1,0,3,8]
- Output:
- [-4,0,3,8]
- Explanation:
Only -1 repeats. Result: -4, 0, 3, 8.
Constraints
0 ≤ chain length ≤ 105
-1000 ≤ node value ≤ 1000
the values are in non-decreasing order
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)