Merge K sorted linked lists

Hard

Problem

Given k sorted linked lists, merge them into one sorted list and return its head.

Example 1

Input:  [1→4→5, 1→3→4, 2→6]
Output: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Also asked as: Merge K sorted Linked list

Test cases

Case 1

Input:    [[1,4,5],[1,3,4],[2,6]]
Expected: [1,1,2,3,4,4,5,6]

Case 2

Input:    []
Expected: []

Case 3

Input:    [[]]
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Divide and conquer (pairwise merge)

Time O(N log k)Space O(log k)

Merge lists in pairs, halving the count each round — like merge sort over the array of lists.

function mergeKLists(lists) {
const merge2 = (a, b) => {
const d = { next: null }; let t = d;
while (a && b) { if (a.val <= b.val) { t.next = a; a = a.next; } else { t.next = b; b = b.next; } t = t.next; }
t.next = a || b;
return d.next;
};
if (!lists.length) return null;
while (lists.length > 1) {
const merged = [];
for (let i = 0; i < lists.length; i += 2)
merged.push(merge2(lists[i], lists[i + 1] || null));
lists = merged;
}
return lists[0];
}

A min-heap of the k current heads also gives O(N log k).