How Do You Merge K Sorted Linked Lists?
Learn how to merge k sorted linked lists in O(N log k) time using a min-heap, with a full Python example.
Expected Interview Answer
K sorted linked lists are merged efficiently in O(N log k) time by using a min-heap of size k that always holds the current head of each list, repeatedly popping the smallest node and pushing its successor, where N is the total number of nodes across all lists.
Seed the heap with the head node of each of the k lists, keyed by node value. On each step, pop the smallest node from the heap, append it to the result list, and if that node has a next node, push the successor into the heap. This repeats until the heap is empty, doing N total pops and pushes, each costing O(log k), giving O(N log k) overall with only O(k) extra space for the heap. A divide-and-conquer alternative pairs up lists and merges them two at a time in a binary reduction, also achieving O(N log k) since there are log k merge rounds and each round processes all N nodes. Naively merging lists one at a time into a running result gives O(N * k), which is worse whenever k is more than a small constant.
- O(N log k) time using a min-heap of size k
- O(k) extra space, independent of total node count
- Divide-and-conquer variant matches the same complexity
- Both avoid the O(N * k) cost of sequential pairwise merging
AI Mentor Explanation
Merging k sorted lists is like combining k separately sorted stacks of scorecards from k different grounds into one master sorted stack. Instead of comparing all k stacks' top cards by eye each time, you keep the k top cards in a small priority tray that always surfaces the lowest score; you take that card, place it on the master stack, then refill the tray from whichever ground's stack it came from. Because the tray only ever holds k cards, each pick-and-refill costs proportional to log k, and you repeat this for every card across all grounds. This beats merging the stacks two grounds at a time in sequence, which would redo comparisons far more often as the master stack grows.
Step-by-Step Explanation
Step 1
Seed a min-heap with k heads
Push the head node of every list into a min-heap keyed by node value, size at most k.
Step 2
Pop the smallest node
Remove the minimum from the heap and append it to the merged result list.
Step 3
Push its successor
If the popped node has a next node, push that successor into the heap.
Step 4
Repeat until the heap is empty
N total pops/pushes at O(log k) each give O(N log k) time overall.
What Interviewer Expects
- Propose the min-heap-of-size-k approach with correct complexity O(N log k)
- Know the divide-and-conquer pairwise-merge alternative and why it matches the same complexity
- Reject naive sequential merging as O(N * k)
- Correctly handle empty input lists and lists of different lengths
Common Mistakes
- Merging lists two at a time sequentially, giving O(N * k) instead of O(N log k)
- Forgetting to push the popped node's successor back into the heap
- Not handling empty lists among the k inputs
- Miscounting the heap size as k when it should track only currently active list heads
Best Answer (HR Friendly)
“I keep a small heap that always holds the current smallest head node across all k lists. I keep popping the smallest, appending it to the result, and pushing in whatever came next from that same list, which merges everything in O(N log k) time using only O(k) extra memory.”
Code Example
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode()
tail = dummy
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextFollow-up Questions
- How would the divide-and-conquer pairwise merge approach work instead of a heap?
- Why does naive sequential merging cost O(N * k)?
- How would you adapt this to merge k sorted arrays instead of linked lists?
- How would you handle ties in value across different lists in the heap comparator?
MCQ Practice
1. What is the time complexity of merging k sorted linked lists with a min-heap of size k?
Each of the N total nodes triggers one O(log k) heap operation, giving O(N log k) overall.
2. What is pushed into the heap immediately after popping a node during the merge?
The popped node's next node (if any) is pushed to keep that list's next candidate in the heap.
3. What is the extra space complexity of the min-heap approach, excluding the output list?
The heap holds at most one node per list at any time, so it never exceeds O(k) size.
Flash Cards
What structure merges k sorted linked lists efficiently? — A min-heap of size k holding the current head of each list.
What is the time complexity of the heap-based merge? — O(N log k), where N is the total number of nodes.
What happens after popping a node from the heap? — Its successor, if any, is pushed into the heap to replace it.
What complexity does naive sequential pairwise merging give? — O(N * k), worse than the heap or divide-and-conquer approach for large k.