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]A brute-force approach would concatenate all lists and then sort the combined list, which is inefficient. Instead, the algorithm merges pairs of lists iteratively. Initially, it merges the first two lists: [1,4,5] and [1,3,4] into [1,1,3,4,4,5]. Then it merges this result with the third list [2,6], producing the final sorted list [1,1,2,3,4,4,5,6]. This pairwise merging reduces the problem size logarithmically, improving efficiency.
Approach
Straightforward Solution
A naive solution concatenates all lists into one and sorts it, resulting in O(N log N) time where N is the total number of nodes. This is inefficient given the sorted nature of the input lists.
Core Observation
Merging two sorted linked lists can be done efficiently in O(n) time by iterating through both lists simultaneously. Extending this to k lists suggests a divide and conquer approach where pairs of lists are merged repeatedly until only one remains.
Path to Optimal
PreviewRecognizing that merging two sorted lists is efficient, the problem reduces to repeatedly merging pairs of lists. By merging lists in pairs, the number of lists halves each iteration, leading to a logarithmic number of merge rounds…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIteratively merge pairs of lists until only one list remains. In each iteration, merge lists at indices i and i+1, append the merged list to a new list, and replace the original list array with this new 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 merge operation processes all nodes once, and the number of merge rounds is log k because the number of lists halves each iteration. Thus, total time is O(N log k).
Space
O(1) auxiliary space
The merging is done in-place by rearranging pointers without allocating new nodes, so only constant extra space is used aside from the input and output lists.
Pattern Spotlight
Divide and Conquer (Pairwise Merging)
When merging multiple sorted sequences, repeatedly merge pairs to halve the problem size each round, leveraging the efficiency of merging two sorted lists and achieving logarithmic rounds of merging.
Solution
| 1 | class Solution:
|
| 2 | def mergeKLists(self, lists: list[ListNode]) -> ListNode:
|
| 3 | if not lists or len(lists) == 0:
|
| 4 | return None
|
| 5 |
|
| 6 | while len(lists) > 1:
|
| 7 | merged_lists = []
|
| 8 | for i in range(0, len(lists), 2):
|
| 9 | l1 = lists[i]
|
| 10 | l2 = lists[i + 1] if (i + 1) < len(lists) else None
|
| 11 | merged_lists.append(self.mergeList(l1, l2))
|
| 12 | lists = merged_lists
|
| 13 | return lists[0]
|
| 14 |
|
| 15 | def mergeList(self, l1, l2):
|
| 16 | dummy = ListNode()
|
| 17 | tail = dummy
|
| 18 | while l1 and l2:
|
| 19 | if l1.val < l2.val:
|
| 20 | tail.next = l1
|
| 21 | l1 = l1.next
|
| 22 | else:
|
| 23 | tail.next = l2
|
| 24 | l2 = l2.next
|
| 25 | tail = tail.next
|
| 26 | if l1:
|
| 27 | tail.next = l1
|
| 28 | if l2:
|
| 29 | tail.next = l2
|
| 30 | return dummy.next |
Step-by-Step Solution
Iteratively Merge Lists in Pairs Until One Remains
| 3 | if not lists or len(lists) == 0:
|
| 4 | return None
|
| 6 | while len(lists) > 1:
|
| 7 | merged_lists = []
|
| 8 | for i in range(0, len(lists), 2):
|
| 9 | l1 = lists[i]
|
| 10 | l2 = lists[i + 1] if (i + 1) < len(lists) else None
|
| 11 | merged_lists.append(self.mergeList(l1, l2))
|
| 12 | lists = merged_lists
|
| 13 | return lists[0]
|
Objective
To reduce the array of k sorted lists to a single sorted list by merging pairs iteratively.
Key Insight
Merging two sorted lists is efficient, so merging pairs repeatedly reduces the problem size exponentially. Each iteration halves the number of lists, ensuring the total number of merge operations grows logarithmically with k. This approach leverages the divide and conquer principle to optimize performance.
Interview Quick-Check
Core Logic
Repeatedly merge pairs of lists to halve the number of lists each iteration, continuing until only one merged list remains.
State & Boundaries
Handle odd number of lists by merging the last list with None, effectively leaving it unchanged.
Common Pitfalls & Bugs
Failing to update the lists array after each merge round or incorrectly handling the last list when the number of lists is odd.
Complexity
This iterative pairwise merging ensures O(N log k) time complexity, where N is total nodes and k is initial number of lists.
Merge Two Sorted Linked Lists into One Sorted List
To merge two sorted linked lists efficiently by iterating through both and linking nodes in ascending order.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if not lists or len(lists) == 0:Check if the input list array is empty or None.
This early exit handles edge cases where no lists are provided, preventing unnecessary computation and returning None as specified.
return NoneReturn None immediately if input is empty.
Returning None here correctly signals that there is no merged list to produce when input is empty.
Full line-by-line criticality + rationale for all 25 lines available on Pro.
Test Your Understanding
Why does merging pairs of lists repeatedly reduce the overall time complexity compared to merging lists sequentially?
See the answer with Pro.
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