1596. Nearly Sorted Two-Way Chain
A doubly linked list of sensor readings is almost in order: after a stable sort, every node sits at most k positions away from where it started. Write nearlySortedChain(head, k), which returns the list sorted in non-decreasing order of value, with equal values keeping their original relative order, by relinking the existing nodes and keeping both next and prev correct. Use a min-heap that holds at most k + 1 candidates, each ordered by value and then by original index, instead of a full sort. The list has 0 to 1000 nodes, 0 <= k < max(length, 1), and the displacement promise always holds. Aim for O(n log k) time and O(k) extra space.
Example 1
- Input:
- head = [2,1,4,3,6,5], k = 1
- Output:
- [1,2,3,4,5,6]
- Explanation:
Each pair is out of order by one place, so k = 1 suffices.
Example 2
- Input:
- head = [3,1,2,6,4,5], k = 2
- Output:
- [1,2,3,4,5,6]
- Explanation:
The value 3 is two places before its sorted slot.
Example 3
- Input:
- head = [1,2,3], k = 0
- Output:
- [1,2,3]
- Explanation:
Already sorted with k = 0.
Constraints
0 ≤ length ≤ 1000
0 ≤ k < max(length, 1)
every node is at most k positions from its place in the stable sorted 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 log k)
- Space
- O(k)