Merge k Sorted Lists
The key idea
At every moment the next node of the answer must be the smallest current head across all
k lists. A min-heap keyed by node value gives that smallest head in O(log k); pop it, append it, then push its successor. This beats scanning all k heads each step.Problem
You are given an array of k linked-lists lists, where each list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return its head.
The number of lists k can be 0 (an empty lists), and any individual list lists[i] can itself be empty, in which case the merged result is an empty list (null).
Constraints
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]is sorted in ascending order.- The sum of
lists[i].lengthwill not exceed10^4.
Examples
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Input: lists = []
Output: []
Input: lists = [[]]
Output: []
Complexity
Time: O(N log k) Space: O(k)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM