328. Sort the Chain
A depot keeps its freight cars on a single track modelled as a chain: each node holds the cargo weight of one car and a link to the next car, and head is the first car. The cars are in no particular order, and the dispatcher wants them lined up from the lightest to the heaviest.
Return the head of the chain after sorting it into non-decreasing order of weight. Cars with equal weights are interchangeable. You can only move forward through the links, so there is no random access like in an array, and the chain may hold up to 100,000 cars; a quadratic method will be too slow. Try to find a method that takes O(n log n) time and does not copy the cars into a big array.
Example 1
- Input:
- head = [44,-7,19,0,19,3]
- Output:
- [-7,0,3,19,19,44]
- Explanation:
Sorted from lightest to heaviest: -7, 0, 3, 19, 19, 44.
Example 2
- Input:
- head = [90,80,70]
- Output:
- [70,80,90]
- Explanation:
The chain is in descending order, so it is simply reversed: 70, 80, 90.
Constraints
0 ≤ chain length ≤ 105
-105 ≤ node value ≤ 105
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 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(log n)