Merging k sorted linked lists sounds straightforward at first. Just merge them one by one, right? But with k potentially being 10,000 lists, that naive approach becomes painfully slow. This problem is all about finding the right strategy to minimize comparisons.
The breakthrough for me was realizing this is a perfect use case for either a min-heap or divide-and-conquer. Both approaches dramatically improve performance by being smart about which elements we compare.
Understanding the Problem
We're given an array of k linked lists, where each list is already sorted in ascending order. Our task is to merge all of them into a single sorted linked list.
Here are the constraints:
- k == lists.length
- 0 <= k <= 10^4 (up to 10,000 lists!)
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order
- The sum of lists[i].length will not exceed 10^4
Example 1:
- Input:
lists = [[1,4,5],[1,3,4],[2,6]] - Output:
[1,1,2,3,4,4,5,6]
Example 2:
- Input:
lists = [] - Output:
[]
Example 3:
- Input:
lists = [[]] - Output:
[]
My First Approach: Merge One by One
My initial thought was simple: take the first list, merge it with the second, then merge that result with the third, and so on.
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
// Merge two sorted lists
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}
// Merge lists one by one
let result = lists[0];
for (let i = 1; i < lists.length; i++) {
result = mergeTwoLists(result, lists[i]);
}
return result;
}
This works, but it's inefficient. Let's say we have k lists, each with n nodes.
Time Complexity: O(k² × n)
- First merge: n + n = 2n
- Second merge: 2n + n = 3n
- Third merge: 3n + n = 4n
- ...and so on
- Total: n + 2n + 3n + ... + kn = n(1 + 2 + 3 + ... + k) = O(k² × n)
For k = 10,000, this becomes extremely slow!
The Divide and Conquer Insight
Looking at the time complexity, I realized the problem is that we keep re-processing nodes. What if instead of merging sequentially, we pair up lists and merge them, then pair up the results and merge again?
Think of it like a tournament bracket:
- Round 1: Merge list[0] with list[1], list[2] with list[3], etc.
- Round 2: Merge the results from round 1
- Continue until we have one list
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}
// Divide and conquer
while (lists.length > 1) {
const mergedLists = [];
for (let i = 0; i < lists.length; i += 2) {
const l1 = lists[i];
const l2 = i + 1 < lists.length ? lists[i + 1] : null;
mergedLists.push(mergeTwoLists(l1, l2));
}
lists = mergedLists;
}
return lists[0];
}
Time Complexity: O(N log k)
- We have log k levels (each level halves the number of lists)
- At each level, we process all N nodes total
- Total: O(N log k)
Space Complexity: O(1) if we don't count the output
This is much better! Let me trace through an example with lists = [[1,4,5],[1,3,4],[2,6]]:
Round 1: Merge pairs
- Merge [1,4,5] and [1,3,4] → [1,1,3,4,4,5]
- Merge [2,6] and null → [2,6]
- After round 1:
[[1,1,3,4,4,5], [2,6]]
Round 2: Merge pairs
- Merge [1,1,3,4,4,5] and [2,6] → [1,1,2,3,4,4,5,6]
- After round 2:
[[1,1,2,3,4,4,5,6]]
Done! We have one merged list.
Wait, What About Using a Min-Heap?
After solving it with divide-and-conquer, I started thinking about another approach. At any point, we only need to find the smallest value among the current heads of all k lists. That's exactly what a min-heap is great at!
The idea:
- Put the first node from each list into a min-heap
- Extract the minimum (this is our next node)
- If that node has a next node, add it to the heap
- Repeat until the heap is empty
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
// Min-heap implementation using array
class MinHeap {
constructor() {
this.heap = [];
}
push(node) {
this.heap.push(node);
this.bubbleUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return min;
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].val >= this.heap[parentIndex].val) break;
[this.heap[index], this.heap[parentIndex]] =
[this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
bubbleDown(index) {
while (true) {
let smallest = index;
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
if (leftChild < this.heap.length &&
this.heap[leftChild].val < this.heap[smallest].val) {
smallest = leftChild;
}
if (rightChild < this.heap.length &&
this.heap[rightChild].val < this.heap[smallest].val) {
smallest = rightChild;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] =
[this.heap[smallest], this.heap[index]];
index = smallest;
}
}
isEmpty() {
return this.heap.length === 0;
}
}
const heap = new MinHeap();
// Add first node from each list to heap
for (const list of lists) {
if (list) heap.push(list);
}
const dummy = new ListNode(0);
let current = dummy;
// Extract min and add next nodes
while (!heap.isEmpty()) {
const node = heap.pop();
current.next = node;
current = current.next;
if (node.next) {
heap.push(node.next);
}
}
return dummy.next;
}
Time Complexity: O(N log k) where N is total number of nodes
- Each of N nodes is inserted and extracted from heap once
- Each heap operation takes O(log k) time
- Total: O(N log k)
Space Complexity: O(k) for the heap
This is much better! For k = 10,000 and N = 10,000, we go from billions of operations to just hundreds of thousands.
Comparing the Two Approaches
Both optimized solutions have O(N log k) time complexity, but they have different trade-offs:
| Approach | Time Complexity | Space Complexity | Pros | Cons |
|---|---|---|---|---|
| Divide and conquer | O(N log k) | O(1) | Simple, less space | Need mergeTwoLists helper |
| Min-heap | O(N log k) | O(k) | Incremental processing | More complex, O(k) space |
I prefer divide-and-conquer because:
- Uses less space
- Simpler to understand and implement
- You probably already know how to merge two lists
But min-heap is great when:
- You're comfortable with heap data structures
- You want to process nodes incrementally
- Space for k nodes is acceptable
Common Pitfalls
When implementing these solutions, watch out for:
-
Null checks: Always handle empty lists, null lists, and lists containing only empty lists.
-
Edge cases:
- Empty input array:
lists = [] - Array with one empty list:
lists = [[]] - Array with mix of empty and non-empty lists
- Empty input array:
-
Heap implementation: If implementing your own heap, make sure your comparisons are correct (min-heap uses < not >).
-
Off-by-one errors: In divide-and-conquer, when pairing lists, handle odd numbers of lists correctly.
-
Dummy node: Using a dummy node makes the code much cleaner. Don't forget to return
dummy.next, notdummy.
Key Takeaways
- Naive sequential merging is O(k² × n), which is too slow for large k
- Both min-heap and divide-and-conquer achieve O(N log k)
- Min-heap: straightforward but uses O(k) space
- Divide and conquer: more space-efficient with O(1) space
- Understanding why the naive approach is slow helps you appreciate the optimization
- The divide-and-conquer pattern appears in many problems (like merge sort)
- Always consider the constraints: k can be very large here, which rules out O(k²) solutions
This problem really taught me that the first working solution isn't always acceptable. When k is large, the difference between O(k² × n) and O(N log k) is the difference between timing out and passing. Always analyze your complexity and consider whether there's a better approach for the given constraints.