Problem Understanding
lists holds k linked lists, each already sorted in ascending order.
Combine them into a single linked list that is also sorted in ascending order, and return its head.
Example:
- Input:
lists = [[1,4,5],[1,3,4],[2,6]] - Output:
[1,1,2,3,4,4,5,6]
Algorithm Strategy
Min-Heap Approach (O(N log k))
Instead of comparing the heads of all k lists at every step (which takes O(k)), we can use a Min-Heap.
- Initialize: Push the head node of every non-empty list into a Min-Heap.
- Iterate: While heap is not empty:
- Pop the smallest node (root) from heap.
- Add this node to our result list.
- If the popped node has a
nextnode, push thatnextnode into the heap.
- Result: The result list is sorted.
Interactive Visualization
The k lists as chains, the min-heap holding the front node of each, and the result growing from a dummy node. Each pop links the smallest node into the result and pushes the node after it.
Dry Run
Lists: L1: [1,4,5], L2: [1,3,4], L3: [2,6]. A node is written value·list.
| Step | Pop | Push next | Heap after (root first) | Result |
|---|---|---|---|---|
| Init | - | heads 1·L1, 1·L2, 2·L3 | [1·L1, 1·L2, 2·L3] |
dummy |
| 1 | 1·L1 | 4·L1 | [1·L2, 2·L3, 4·L1] |
1 |
| 2 | 1·L2 | 3·L2 | [2·L3, 4·L1, 3·L2] |
1 → 1 |
| 3 | 2·L3 | 6·L3 | [3·L2, 4·L1, 6·L3] |
1 → 1 → 2 |
| 4 | 3·L2 | 4·L2 | [4·L1, 6·L3, 4·L2] |
… → 2 → 3 |
| 5 | 4·L1 | 5·L1 | [4·L2, 6·L3, 5·L1] |
… → 3 → 4 |
| 6 | 4·L2 | - (L2 ends) | [5·L1, 6·L3] |
… → 4 → 4 |
| 7 | 5·L1 | - (L1 ends) | [6·L3] |
… → 4 → 5 |
| 8 | 6·L3 | - (L3 ends) | [] |
1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 |
Edge Cases
- No lists (
[]): the heap starts empty anddummy.nextis null. - Empty lists inside (
[[], [1]]): only non-null heads are pushed — a null would break the comparison. - One list: the heap holds one node at a time and the list comes back unchanged.
- Equal values: any order among equal nodes gives the same merged values. Python adds the list index
ito each tuple so a tie never falls through to comparing two nodes.
Solution
A min-heap of list heads in every language. JavaScript, TypeScript and C carry a small heap of their own.
Merge K Sorted Lists Code
1class Heap {2 constructor(before) {3 this.items = [];4 this.before = before;5 }67 size() {8 return this.items.length;9 }1011 peek() {12 return this.items[0];13 }1415 push(item) {16 const a = this.items;17 a.push(item);18 let i = a.length - 1;19 while (i > 0 && this.before(a[i], a[(i - 1) >> 1])) {20 const parent = (i - 1) >> 1;21 [a[i], a[parent]] = [a[parent], a[i]];22 i = parent;23 }24 }2526 pop() {27 const a = this.items;28 const top = a[0];29 const last = a.pop();30 if (a.length > 0) {31 a[0] = last;32 let i = 0;33 while (true) {34 const left = 2 * i + 1, right = 2 * i + 2;35 let first = i;36 if (left < a.length && this.before(a[left], a[first])) first = left;37 if (right < a.length && this.before(a[right], a[first])) first = right;38 if (first === i) break;39 [a[i], a[first]] = [a[first], a[i]];40 i = first;41 }42 }43 return top;44 }45}4647var mergeKLists = function(lists) {48 const heap = new Heap((a, b) => a.val < b.val);49 for (const node of lists) {50 if (node) heap.push(node);51 }52 const dummy = new ListNode(0);53 let tail = dummy;54 while (heap.size() > 0) {55 const node = heap.pop();56 tail.next = node;57 tail = node;58 if (node.next) heap.push(node.next);59 }60 return dummy.next;61};