326. Insertion Order Chain
A card dealer holds a chain of cards, each node carrying the card's rank and a link to the next card, with head as the first card. He sorts them the way people sort a hand: he keeps a sorted pile at the front, takes the next unsorted card, and slides it into the correct place inside the pile.
Return the head of the chain after sorting it into non-decreasing order using this insertion approach, relinking the existing nodes instead of creating new ones. Cards with equal ranks must keep their original relative order. Since you can only walk forward in a chain, think about how to avoid walking from the beginning of the pile every time when the next card is already large enough to go at the end of the pile.
Example 1
- Input:
- head = [23,4,15,4,8]
- Output:
- [4,4,8,15,23]
- Explanation:
Pile grows: 23 | 4, 23 | 4, 15, 23 | 4, 4, 15, 23 | 4, 4, 8, 15, 23.
Example 2
- Input:
- head = [-2,0,6,9]
- Output:
- [-2,0,6,9]
- Explanation:
The chain is already sorted, so each new card is simply appended behind the pile: -2, 0, 6, 9.
Constraints
0 ≤ chain length ≤ 5000
-1000 ≤ node value ≤ 1000
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^2)
- Space
- O(1)