Merge K Sorted Lists
Merge K Sorted Lists is a hard Linked List problem from the Blind 75. The key pattern is min-heap or divide and conquer, and a good solution runs in O(N log k) time.
Problem
Merge every non-decreasing linked-list value array into one non-decreasing result.
Examples
Example 1
Input
[[1,8],[2,3,10],[],[4,6]]Output
[1,2,3,4,6,8,10]Example 2
Input
[]Output
[]Example 3
Input
[[2,4],[1,5,9],[3]]Output
[1,2,3,4,5,9]Approach
Keep the current front of every list in a min-heap and repeatedly take the smallest, or merge lists in pairs until one remains.
| Pattern | Min-heap or divide and conquer |
|---|---|
| Time | O(N log k) |
| Space | O(k) |
Watch out for
Some of the lists can be empty, and so can the whole input.