312. Dedupe the Chain
A sensor logs readings into a chain, and the readings are stored in non-decreasing order. Because of a glitch, the same reading was often logged several times in a row, and the archive only needs one copy of each distinct reading.
Given the head of the sorted chain, delete the extra nodes so that every value appears exactly once, and return the head of the result. The first node of each run of equal values is the one that stays. The chain may be empty and can hold up to 100,000 nodes; no extra chain should be built.
Example 1
- Input:
- head = [2,2,5,8,8,8,11,11]
- Output:
- [2,5,8,11]
- Explanation:
Runs of 2, 8 and 11 shrink to one node each, giving 2, 5, 8, 11.
Example 2
- Input:
- head = [-4,-4,-4]
- Output:
- [-4]
- Explanation:
All nodes are equal, so only one remains.
Constraints
0 ≤ chain length ≤ 105
-104 ≤ node value ≤ 104
The chain is sorted 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.
Expected complexity
- Time
- O(n)
- Space
- O(1)