Merge k Sorted Lists
Problem
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.
- k == lists.length
- 0 ≤ k ≤ 10⁴
- 0 ≤ lists[i].length ≤ 500
- −10⁴ ≤ lists[i][j] ≤ 10⁴
- lists[i] is sorted in ascending order.
- The sum of lists[i].length won't exceed 10⁴.
Example
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]The brute-force approach concatenates all lists and sorts them, which is inefficient. Instead, the algorithm uses a min-heap to efficiently track the smallest current node among all lists. Initially, the heap contains the first node of each list. The algorithm repeatedly extracts the smallest node from the heap, appends it to the merged list, and if the extracted node has a next node, it pushes that next node into the heap. This process continues until the heap is empty, resulting in a fully merged sorted list.
Approach
Straightforward Solution
A naive approach concatenates all nodes into one list and sorts it, resulting in O(N log N) time where N is the total number of nodes. This is inefficient for large inputs.
Core Observation
Merging k sorted lists requires repeatedly selecting the smallest current element among the heads of all lists. This is a classic problem of efficiently merging multiple sorted sequences.
Path to Optimal
PreviewThe key insight is to use a min-heap (priority queue) to keep track of the smallest current node among the k lists. By pushing the first node of each list into the heap, the algorithm can extract the minimum node in O(log k) time and then push the next node from that list…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a min-heap to store the current nodes of each list. Initialize the heap with the first node of each non-empty list…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(N log k)
Each of the N nodes is pushed and popped from the heap at most once. Each heap operation takes O(log k) time because the heap size is at most k.
Space
O(k)
The heap stores at most one node from each of the k lists at any time, resulting in O(k) auxiliary space.
Pattern Spotlight
Heaps (Priority Queue for Merging Sorted Sequences)
When merging multiple sorted sequences, maintain a min-heap of the current smallest elements from each sequence to efficiently extract the global minimum and advance pointers, reducing the problem from O(N log N) to O(N log k).
Solution
| 1 | import heapq |
| 2 | |
| 3 | class Solution: |
| 4 | def mergeKLists(self, lists: list[ListNode]) -> ListNode: |
| 5 | heap = [] |
| 6 | |
| 7 | for source, head in enumerate(lists): |
| 8 | if head is not None: |
| 9 | heapq.heappush(heap, (head.val, source, head)) |
| 10 | |
| 11 | dummy = ListNode() |
| 12 | tail = dummy |
| 13 | |
| 14 | while heap: |
| 15 | _, source, node = heapq.heappop(heap) |
| 16 | next_node = node.next |
| 17 | |
| 18 | tail.next = node |
| 19 | tail = node |
| 20 | tail.next = None |
| 21 | |
| 22 | if next_node is not None: |
| 23 | heapq.heappush(heap, (next_node.val, source, next_node)) |
| 24 | |
| 25 | return dummy.next |
Step-by-Step Solution
Initialize Min-Heap with the First Node of Each List
| 1 | import heapq |
| 5 | heap = [] |
| 7 | for source, head in enumerate(lists): |
| 8 | if head is not None: |
| 9 | heapq.heappush(heap, (head.val, source, head)) |
| 11 | dummy = ListNode() |
| 12 | tail = dummy |
Objective
To prepare a min-heap containing the first node of each non-empty linked list for efficient minimum extraction.
Key Insight
By pushing the first node of each list into the heap, the algorithm sets up a data structure that always contains the smallest current candidates from all lists. This enables efficient retrieval of the next smallest node to append to the merged list. The heap stores tuples of (node value, source list index, node) to handle nodes with equal values and maintain stable ordering.
Interview Quick-Check
Core Logic
The heap stores tuples with node value and source index to ensure correct ordering and to distinguish nodes with identical values.
Common Pitfalls & Bugs
Forgetting to check if a list is empty before pushing its head into the heap can cause errors.
State & Boundaries
Only non-null heads are pushed into the heap to avoid invalid entries.
Build the Merged List by Extracting Minimum Nodes and Pushing Next Nodes
To iteratively extract the smallest node from the heap, append it to the merged list, and push the next node from the same list into the heap if it exists.
Return the Head of the Fully Merged Sorted List
To return the merged linked list starting from the node following the dummy head.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
heapq.heappush(heap, (head.val, source, head))Push the tuple (node value, source index, node) into the heap.
Storing the node value as the first element ensures the heap orders nodes by their values. Including the source index breaks ties when values are equal, preventing comparison errors between ListNode objects.
_, source, node = heapq.heappop(heap)Pop the smallest node tuple from the heap.
Extracting the minimum node maintains the sorted order of the merged list by always selecting the next smallest element.
if next_node is not None:If the next node exists, push it into the heap.
Pushing the successor node maintains the heap invariant and ensures all nodes from each list are eventually merged.
Full line-by-line criticality + rationale for all 16 lines available on Pro.
Test Your Understanding
Why does using a min-heap reduce the time complexity from O(N log N) to O(N log k)?
See the answer with Pro.
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Merge k Sorted Lists from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Merge k Sorted Lists drill