Merge k Sorted Lists
Understanding the Problem
We have k linked lists, each already sorted, and we need to merge them into a single sorted linked list. This generalizes the "merge two sorted lists" problem from two inputs to k inputs.
Because each list is sorted, the next element of the merged result is always the smallest among the current heads of the k lists. The work, then, is finding that minimum repeatedly. Scanning all k heads each time costs O(k) per element. A min-heap returns the minimum in O(log k) instead.
A second strategy is divide and conquer. Instead of merging all k lists at once, pair them up, merge each pair, then pair up the results and repeat. This mirrors the merge phase of merge sort and reaches the same time complexity as the heap.
Key Constraints:
0 <= k <= 10^4→ k can be large, and k can be 0, so an empty input array must return null without crashing.The sum of lists[i].length will not exceed 10^4→ The total number of nodes N is at most 10,000, which is what drives the time complexity.-10^4 <= lists[i][j] <= 10^4→ Node values fit in a 32-bit signed integer, so comparisons never overflow.
Approach 1: Brute Force (Collect and Sort)
Intuition
Ignore the linked list structure entirely. Walk through every node in every list, collect all the values into a single array, sort that array, then build a new linked list from the sorted values.
This discards the fact that the input lists are already sorted, but it produces a correct answer and serves as a baseline to improve on.
Algorithm
- Traverse all k linked lists and collect every node value into an array.
- Sort the array.
- Create a new linked list from the sorted array.
- Return the head of the new list.
Example Walkthrough
Code
- Time Complexity: O(N log N). Collecting all N values takes O(N). Sorting takes O(N log N). Building the result list takes O(N). The sorting step dominates.
- Space Complexity: O(N). We store all N values in an array, plus we create N new nodes for the output list.
Sorting throws away the sorted structure we were handed and pays O(N log N) to rebuild it. The next approach exploits that structure to pick the smallest element in O(log k) per step.
Approach 2: Min-Heap (Priority Queue)
Intuition
Since each list is sorted, the next element in the merged result is the smallest among the current heads of the k lists. A min-heap holds those heads and returns the smallest in O(log k) per operation, compared to O(k) for scanning all heads.
Push all k initial heads into the heap. Then repeatedly pop the smallest node, append it to the result, and push that node's next pointer back into the heap if it exists. The process ends when the heap is empty.
The heap holds at most one node per list, so it never exceeds k entries. Each list is sorted, so a list's smallest unprocessed node is its current head, and the global minimum across all lists is therefore one of the k heads in the heap. Popping that minimum and pushing only its successor preserves this invariant, so the values come out in non-decreasing order. The k bound on heap size is why each operation costs O(log k) rather than O(log N).
Algorithm
- Create a min-heap (priority queue) that orders nodes by their value.
- Push the head of each non-empty list into the heap.
- While the heap is not empty:
- Pop the node with the smallest value.
- Append it to the result list.
- If that node has a next pointer, push the next node into the heap.
- Return the head of the result list.
Example Walkthrough
Code
- Time Complexity: O(N log k). We process all N nodes. Each node is pushed into and popped from the heap exactly once. Each heap operation is O(log k) where k is the number of lists.
- Space Complexity: O(k). The heap contains at most k nodes at any time. We reuse the existing list nodes for the output.
The next approach reaches the same O(N log k) time without a heap, using only a function that merges two sorted lists.
Approach 3: Divide and Conquer
Intuition
Borrow the structure of merge sort. Pair up the k lists, merge each pair with the standard "merge two sorted lists" routine, and repeat until one list remains.
The first round merges k lists into k/2, the second into k/4, and so on, so after log(k) rounds a single list remains. Within each round, every node is touched once because each node belongs to exactly one of the pairs being merged. That makes a round O(N), and log(k) rounds give O(N log k), matching the heap. The only building block needed is the two-list merge.
Why halving instead of merging one list at a time into an accumulator? Folding each list into a growing accumulator re-scans the accumulator on every step, which gives O(N k) total. Pairing keeps the merged lengths balanced so no node is scanned more than log(k) times.
Algorithm
- If the list of lists is empty, return null.
- While there is more than one list remaining:
- Pair up adjacent lists and merge each pair using the merge-two-sorted-lists algorithm.
- Replace the original list of lists with the merged results.
- Return the single remaining list.
Example Walkthrough
Code
- Time Complexity: O(N log k). There are log(k) rounds of merging, and each round processes all N nodes once, for N * log(k) total.
- Space Complexity: O(1). The code shown merges in place by overwriting slots in the input array and reusing the existing nodes, so it uses only constant extra space. A recursive divide-and-conquer variant would instead use O(log k) stack space.