Approach Summary
Use a min-heap of size k storing (value, list_index, node). Extract min, add to result, push next node from that list.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Divide and Conquer Pairwise Merging | O(N log k) | O(1) iterative | Merge lists in pairs repeatedly, cutting the number of candidate lists in half each round. |
| 2 Approach 2: Min-Heap / Priority Queue (Optimal) | O(N log k) | O(k) | Track the head of each non-empty list in a min-heap of size k, repeatedly extracting the minimum. |
Step 1: Baseline
Approach 1: Divide and Conquer Pairwise Merging
Time: O(N log k)
Space: O(1) iterative
Pair adjacent lists and merge them using our two-list merge subroutine. After the first round, k / 2 lists remain; after the second, k / 4. There are log2(k) rounds, and each round processes all N nodes, giving O(N log k) total work without requiring extra heap data structures.
Approach 1: Divide and Conquer Pairwise Merging Implementation
Approach 1: Divide and Conquer Pairwise Merging
class Solution {
private ListNode mergeTwo(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1; l1 = l1.next;
} else {
tail.next = l2; l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
int step = 1;
while (step < lists.length) {
for (int i = 0; i + step < lists.length; i += step * 2) {
lists[i] = mergeTwo(lists[i], lists[i + step]);
}
step *= 2;
}
return lists[0];
}
}class Solution {
public:
ListNode* mergeTwo(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1; l1 = l1->next;
} else {
tail->next = l2; l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL;
int step = 1;
while (step < lists.size()) {
for (int i = 0; i + step < lists.size(); i += step * 2) {
lists[i] = mergeTwo(lists[i], lists[i + step]);
}
step *= 2;
}
return lists[0];
}
};class Solution:
def mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
def merge_two(l1, l2):
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next, l1 = l1, l1.next
else:
tail.next, l2 = l2, l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
step = 1
while step < len(lists):
for i in range(0, len(lists) - step, step * 2):
lists[i] = merge_two(lists[i], lists[i + step])
step *= 2
return lists[0]function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
function mergeTwo(l1, l2) {
const dummy = new ListNode(0);
let tail = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
tail.next = l1; l1 = l1.next;
} else {
tail.next = l2; l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2;
return dummy.next;
}
let step = 1;
while (step < lists.length) {
for (let i = 0; i + step < lists.length; i += step * 2) {
lists[i] = mergeTwo(lists[i], lists[i + step]);
}
step *= 2;
}
return lists[0];
} Step 2: Most Optimized
Approach 2: Min-Heap / Priority Queue (Optimal)
Time: O(N log k)
Space: O(k)
Place the first node of every list into a priority queue keyed by node value. Pop the smallest node, link it to the growing merged list tail, and if the popped node has a non-null next, push next into the heap. The heap never holds more than k items simultaneously.
Approach 2: Min-Heap / Priority Queue (Optimal) Implementation
Approach 2: Min-Heap / Priority Queue (Optimal)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode element : lists) {
if (element != null) minHeap.add(element);
}
ListNode head = null, tail = null;
while (!minHeap.isEmpty()) {
ListNode curr = minHeap.poll();
if (head == null) {
head = curr; tail = curr;
} else {
tail.next = curr; tail = curr;
}
if (curr.next != null) minHeap.add(curr.next);
}
return head;
}
}class Solution {
public:
struct compare {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> minHeap;
for (ListNode* el : lists) {
if (el != NULL) minHeap.push(el);
}
ListNode* head = NULL;
ListNode* tail = NULL;
while (!minHeap.empty()) {
ListNode* curr = minHeap.top(); minHeap.pop();
if (head == NULL) {
head = curr; tail = curr;
} else {
tail->next = curr; tail = curr;
}
if (curr->next != NULL) minHeap.push(curr->next);
}
return head;
}
};import heapq
class Solution:
def mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]:
min_heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(min_heap, (node.val, i, node))
dummy = ListNode(0)
tail = dummy
while min_heap:
val, i, node = heapq.heappop(min_heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(min_heap, (node.next.val, i, node.next))
return dummy.nextfunction mergeKLists(lists) {
const vals = [];
for (const node of lists) {
let curr = node;
while (curr) {
vals.push(curr.val);
curr = curr.next;
}
}
vals.sort((a, b) => a - b);
const dummy = new ListNode(0);
let tail = dummy;
for (const v of vals) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}Edge Cases to Watch
- Empty lists array (lists = []; returns null)
- lists contains only empty lists (lists = [[], []]; returns null)
- Single list (returns the single list directly)
- Lists of vastly differing lengths
Algorithmic Pattern
View Pattern Guide →
Master the Heap / Priority Queue Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Heap / Priority Queue pattern.
Framework: Heap / Priority Queue • Interview Prep: Tested at FAANG •
Explore all Heap / Priority Queue problems & invariants →
How to Recognize This Pattern
- Merge k sorted sequences
- Heap of k heads
Complexity Analysis
Time Complexity
O(n log k)
Space Complexity
O(k)
Tags
Linked List Heap Divide and Conquer
Frequently Asked Questions
What is the optimal time and space complexity for Merge K Sorted Lists?
The optimal solution for Merge K Sorted Lists achieves O(n log k) runtime complexity and requires O(k) auxiliary space. Time complexity is O(N log k) where N is the total number of nodes across all lists and k is the number of linked lists. Each of the N nodes is pushed and popped from the heap of size k in O(log k) time. Space complexity is O(k) for the priority queue.
How do I identify that Merge K Sorted Lists requires the Heap / Priority Queue pattern?
In technical interviews, look for key problem signals: Merge k sorted sequences; Heap of k heads. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Heap / Priority Queue strategy.
What critical edge cases must be handled in Merge K Sorted Lists?
Essential edge cases to verify include: Empty lists array (lists = []; returns null); lists contains only empty lists (lists = [[], []]; returns null); Single list (returns the single list directly); Lists of vastly differing lengths. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Merge K Sorted Lists?
Merge K Sorted Lists is a Hard-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Google, Microsoft.