ASAPUtils
The frontier invariant
The heap contains the smallest unmerged node from every non-empty source list and no other nodes.
Its minimum is therefore the smallest node remaining anywhere. After popping it, expose only its successor from the same source.
C++ solution
ListNode* mergeKLists(vector<ListNode*>& lists) {
struct Greater {
bool operator()(ListNode* a, ListNode* b) const {
return a->val > b->val;
}
};
priority_queue<ListNode*, vector<ListNode*>, Greater> heap;
for (ListNode* head : lists) if (head) heap.push(head);
ListNode dummy;
ListNode* tail = &dummy;
while (!heap.empty()) {
ListNode* node = heap.top();
heap.pop();
tail->next = node;
tail = node;
if (node->next) heap.push(node->next);
}
return dummy.next;
}
JavaScript solution
class MinHeap {
constructor() { this.a = []; }
get size() { return this.a.length; }
push(node) {
this.a.push(node);
let i = this.a.length - 1;
while (i > 0) {
const p = Math.floor((i - 1) / 2);
if (this.a[p].val <= this.a[i].val) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
pop() {
const root = this.a[0];
const last = this.a.pop();
if (this.a.length) {
this.a[0] = last;
let i = 0;
while (true) {
let smallest = i, l = 2 * i + 1, r = l + 1;
if (l < this.a.length && this.a[l].val < this.a[smallest].val) smallest = l;
if (r < this.a.length && this.a[r].val < this.a[smallest].val) smallest = r;
if (smallest === i) break;
[this.a[i], this.a[smallest]] = [this.a[smallest], this.a[i]];
i = smallest;
}
}
return root;
}
}
function mergeKLists(lists) {
const heap = new MinHeap();
for (const head of lists) if (head) heap.push(head);
const dummy = new ListNode();
let tail = dummy;
while (heap.size) {
const node = heap.pop();
tail.next = node;
tail = node;
if (node.next) heap.push(node.next);
}
return dummy.next;
}
Correctness
The heap minimum is safe to append because every unrepresented successor is at least its represented head. Popping a head and inserting its successor restores the frontier invariant. Repeating until the heap is empty consumes every node in global sorted order.
Complexity
Each of N nodes is pushed and popped once at O(log k) cost: O(N log k) time. The heap stores at most k nodes: O(k) auxiliary space.
Alternative
Pairwise divide-and-conquer merging also gives O(N log k) time and O(log k) recursion depth. It reuses the Merge Two Sorted Lists primitive and is an excellent blank re-solve variant.
Traps
- Pushing every node initially, which grows the heap to N and loses the k-way insight.
- Forgetting to push the popped node’s successor.
- Comparing node objects instead of their values in the heap.
- Confusing k, the number of lists, with N, the total node count.
Blank re-solve prompt
State the frontier invariant, simulate three lists using only their heads, and derive why every node causes exactly one heap push and one pop.