Merge K Sorted Lists hard
Description
You’re given an array of k linked lists, each sorted in ascending order. Merge all of them into one sorted linked list and return it.
Examples
> Case 1:
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
> Case 2:
Input: lists = []
Output: []Constraints
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500- The total number of nodes won’t exceed
10^4.
Why naive merges are too slow
If you merge two lists at a time using the standard two-list merge:
- Merging list 1 and list 2: O(n + m).
- Merging the result with list 3: copies all previous nodes again.
- After K merges, every node has been copied K times.
Total: O(K · N) where N is the total number of nodes. For K = 10⁴ and N = 10⁴, that’s 10⁸ — borderline TLE.
The heap approach
The trick: at every step, which K-way list head has the smallest value? A heap answers that in O(log K).
- Push the head of each input list onto a min-heap (K items).
- Repeatedly pop the smallest head, append it to the output, and push the next node from that same list into the heap.
- When the heap is empty, we’re done.
We process every node once. Each operation is O(log K) (the heap never holds more than K items). Total: O(N log K). For N = K = 10⁴, that’s 130,000 operations — comfortable.
Code
Python gotcha: heapq compares tuple elements in order. If two (val, node) pairs have the same val, Python tries to compare the ListNode objects directly and crashes (ListNode has no __lt__). The fix is the universal trick: insert a unique counter as a tiebreaker between the priority and the payload — (val, counter, node).
Alternative: pairwise merging in a tournament
You can also achieve O(N log K) without a heap by repeatedly merging pairs of lists in a “tournament” — round 1 merges K/2 pairs, round 2 merges K/4 pairs, etc. After log₂(K) rounds you have a single merged list, and every node has been touched O(log K) times.
def merge_two(a, b):
dummy = ListNode(0); tail = dummy
while a and b:
if a.val <= b.val: tail.next = a; a = a.next
else: tail.next = b; b = b.next
tail = tail.next
tail.next = a or b
return dummy.next
def merge_k_lists_pairwise(lists):
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
a = lists[i]
b = lists[i + 1] if i + 1 < len(lists) else None
merged.append(merge_two(a, b))
lists = merged
return lists[0]Same asymptotic cost; sometimes faster in practice because there’s no heap overhead.
Analysis
- Time: O(N log K) — every node enters and exits the heap once at cost O(log K).
- Space: O(K) for the heap (plus the output, which is unavoidable).
This problem is the bridge from “heap as priority queue” to K-way merge — a pattern that shows up in External Merge Sort, Smallest Range Covering Elements, and Ugly Number II.