311. Slot Into Sorted Chain
A cloakroom keeps its tickets on a chain of tags, ordered from the smallest ticket number to the largest, and head is the first tag. A late guest arrives with ticket number value and a new tag must be attached for them so that the chain stays ordered.
Create a new node holding value and splice it into the chain. If some existing nodes already hold the same number, the new node goes after all of them; otherwise it goes directly before the first node whose number is larger. The chain may be empty, in which case the new node becomes the whole chain. Return the head of the resulting chain.
Example 1
- Input:
- head = [12,15,15,31,40], value = 15
- Output:
- [12,15,15,15,31,40]
- Explanation:
The new 15 goes after both existing 15s, so the chain becomes 12, 15, 15, 15, 31, 40.
Example 2
- Input:
- head = [-8,-3,4], value = -20
- Output:
- [-20,-8,-3,4]
- Explanation:
-20 is smaller than everything, so it becomes the new head: -20, -8, -3, 4.
Constraints
0 ≤ chain length ≤ 105
-109 ≤ node value, value ≤ 109
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)