298. Sort 0-1-2 Chain
A paint shop labels cans on a conveyor with three kinds of tag: 0 for light, 1 for medium and 2 for dark. The cans form a chain of nodes whose first can is head, and the tags appear in no particular order.
Rearrange the chain so that all 0 nodes come first, then all 1 nodes, then all 2 nodes, and return the new head. Nodes with the same tag must keep their original relative order. You should do this by relinking the existing nodes, not by building a second chain, and ideally in a single pass over the chain. An empty chain is returned unchanged. Because the chain can hold 100,000 nodes, a general comparison sort that runs in quadratic time is not acceptable.
Example 1
- Input:
- head = [2,0,1,1,2,0,2,1]
- Output:
- [0,0,1,1,1,2,2,2]
- Explanation:
There are two 0s, three 1s and three 2s, so the result is 0, 0, 1, 1, 1, 2, 2, 2.
Example 2
- Input:
- head = [1,2,2,1,2]
- Output:
- [1,1,2,2,2]
- Explanation:
There are no zeros, so the two 1s come first, followed by the three 2s.
Constraints
0 ≤ chain length ≤ 105
node value is 0, 1 or 2
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)