Sort a k-sorted doubly linked list

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}