Linked List · LC #23
Merge K Sorted Lists
Merge k sorted linked lists into one sorted list using a min-heap of size k. O(N log k) time - significantly better than the naive O(Nk) pairwise merge.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Sample I/O
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: 1→1→2→3→4→4→5→6 Input: lists = [] Output: [] Input: lists = [[]] Output: []
Intuition
How to Think About It
Intuition
At any moment, only the current minimum across all k list heads needs to be considered. A min-heap of size k always exposes this minimum in O(log k). Each extracted minimum is appended to the result, and the next node from that list is pushed to the heap - maintaining the invariant. This is the same idea as an external merge sort.
Core Concept
Initialise a min-heap with the heads of all non-null lists. Use a dummy head for the result. Each iteration: pop the minimum node, append to result, push its next (if non-null) to the heap. Repeat until the heap is empty. Time: O(N log k) where N = total nodes across all lists, k = number of lists. Space: O(k) for the heap. Alternative: divide-and-conquer pairwise merge also achieves O(N log k) with O(log k) stack space.
When to use
Merging k sorted sequences (external sort, k-way merge in MapReduce, combining sorted result sets from k database shards).
When NOT to use
When k = 2 - use the simpler Merge Two Sorted Lists directly. When N is tiny - overhead of heap setup may not be worth it.
Key Insights
What to Know Cold
- Min-heap of k elements: each push/pop is O(log k), executed N times → O(N log k) total.
- Naive approach (merge lists one-by-one left to right) is O(Nk) - heap is always better when k > 2.
- Divide-and-conquer (merge pairs of lists repeatedly) also achieves O(N log k) with fewer allocations.
- In Python, push (val, index, node) tuples to the heap since ListNode is not directly comparable.
- For the TypeScript interview solution, collecting all nodes and sorting is O(N log N) - mention it but prefer the heap for O(N log k).
1 example
Worked Examples
Merge 3 sorted lists
[[1,4,5],[1,3,4],[2,6]] → 1→1→2→3→4→4→5→6
Min-heap of size k
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);
for (ListNode l : lists) if (l != null) pq.offer(l);
ListNode dummy = new ListNode(0), curr = dummy;
while (!pq.isEmpty()) {
curr.next = pq.poll();
curr = curr.next;
if (curr.next != null) pq.offer(curr.next);
}
return dummy.next;
}
}Output: 1→1→2→3→4→4→5→6
Canonical hard list problem - tests knowledge of heaps, N-way merge, and ability to compose data structures for optimal complexity.