1576. Two-Way Sorted Slot
A leaderboard is kept as a doubly linked list sorted in non-decreasing order, and a new score must be slotted in without breaking the order. Given head of such a list (each node has val, next and prev) and an integer value, create a new node holding value and insert it after all nodes that are equal to it and before the first node with a greater value. Keep every prev link correct, including the new node's own links and the head's null prev. Return the head of the updated list; the head changes when the new node goes first, and an empty list yields a one-node list. The list has 0 to 1000 nodes. Aim for O(n) time and O(1) extra space.
Example 1
- Input:
- head = [1,3,5,7], value = 4
- Output:
- [1,3,4,5,7]
- Explanation:
4 goes between 3 and 5.
Example 2
- Input:
- head = [2,2,2], value = 2
- Output:
- [2,2,2,2]
- Explanation:
The new 2 goes after all existing 2s.
Example 3
- Input:
- head = [], value = 8
- Output:
- [8]
- Explanation:
Inserting into an empty list gives a one-node list.
Constraints
0 ≤ length ≤ 1000
The list is sorted non-decreasing
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)