329. Split Around X
A warehouse conveyor is modelled as a chain of parcels: each node stores a parcel weight and a link to the next parcel, and head is the first one. Management picks a threshold weight x and wants every parcel lighter than x to travel ahead of every parcel that is x or heavier.
Rearrange the chain accordingly and return its head. The rearrangement must be stable: among the light parcels the original relative order is kept, and among the parcels with weight at least x the original relative order is kept as well. For example, a light parcel that was earlier in the chain than another light parcel must still come first. An empty chain returns an empty chain.
Example 1
- Input:
- head = [14,3,20,7,3,9], x = 9
- Output:
- [3,7,3,14,20,9]
- Explanation:
Values below 9 are 3, 7, 3 (in this order); the rest are 14, 20, 9. Result: 3, 7, 3, 14, 20, 9.
Example 2
- Input:
- head = [50,60,40], x = 45
- Output:
- [40,50,60]
- Explanation:
Only 40 is lighter than 45, so it moves to the front: 40, 50, 60.
Constraints
0 ≤ chain length ≤ 105
-1000 ≤ node value, x ≤ 1000
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)