Sort a k-sorted doubly linked list
Problem
Every node in the doubly linked list is at most k positions away from where it belongs in sorted order. Sort the list efficiently.
Example 1
Input: 3 ⇄ 6 ⇄ 2 ⇄ 12 ⇄ 56 ⇄ 8, k = 2 Output: 2 ⇄ 3 ⇄ 6 ⇄ 8 ⇄ 12 ⇄ 56
Also asked as: Sort a “k”sorted Doubly Linked list
Test cases
Case 1
Input: [3,6,2,12,56,8], 2 Expected: [2,3,6,8,12,56]
Case 2
Input: [2,1,4,3], 1 Expected: [1,2,3,4]
Case 3
Input: [1,2,3], 0 Expected: [1,2,3]
Case 4
Input: [5], 3 Expected: [5]
View solutionHide solution1 approach
1. Min-heap of size k+1
Time O(n log k)Space O(k)
Each element is at most k positions from its sorted spot, so a sliding min-heap of size k+1 yields elements in order.
function sortKSortedDLL(head, k) { const heap = []; // simple sorted array as a min-heap const push = (v) => { let i = heap.findIndex((x) => x > v); i === -1 ? heap.push(v) : heap.splice(i, 0, v); }; let node = head; for (let i = 0; i <= k && node; i++) { push(node.val); node = node.next; } let write = head; while (heap.length) { write.val = heap.shift(); write = write.next; if (node) { push(node.val); node = node.next; } } return head;}