Nearly Sorted Chain
HardLinked List
Problem
Sensor packets arrive almost in order: network jitter can delay or advance a packet, but never by more than k positions. The packets sit in a singly linked list.
Formally, every node is at most k positions away from where it belongs in the sorted order. Given the head and k, return the list sorted in non-decreasing order, in O(n log k) time, by relinking the nodes.
Example 1
- Input:
- head = [3, 1, 2, 6, 4, 5], k = 2
- Output:
- [1, 2, 3, 4, 5, 6]
3 belongs at index 2, two places away; every other node is at most two places away too.
Example 2
- Input:
- head = [2, 1, 4, 3], k = 1
- Output:
- [1, 2, 3, 4]
Constraints
- 0 ≤ number of nodes ≤ 10^5
- 0 ≤ k < max(1, number of nodes)
- -10^9 ≤ node.val ≤ 10^9
- Every node is at most k positions from its sorted position.
Hint
Show the first hint
Full merge sort costs O(n log n) and ignores the promise about k. What does the promise tell you about the smallest node?
Walkthrough
How to approach it
01Clarify before coding
- What does 'k positions away' mean exactly? A node's index in the input and its index in the sorted output differ by at most k.
- Can k be 0? Yes: the list is already sorted.
- Duplicates? Allowed; any order among equal values is fine since only values are compared.
02Brute force
Run a general linked-list merge sort.
Cost: O(n log n) time: correct, but wastes the k promise; when k is tiny (say 3 for 10^5 nodes) a heap of 4 nodes is far cheaper.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.