23. Merge k Sorted Lists
You're handed k linked lists at once, each one already sorted in non-decreasing order, and you must combine them all into a single sorted list.
Your function receives an array lists of k integer arrays (each array holds one list's node values in order; an inner array may be empty, and k itself may be 0) and returns one array containing every value from every list, sorted.
Merging two sorted lists is the easy warm-up — the interesting question here is how to stay efficient when there are many lists: at every step, which of the k front nodes is the smallest?
Example 1:
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: The three sorted lists [1,4,5], [1,3,4], [2,6] combine into one sorted list of all eight values.
Example 2:
Input: lists = []
Output: []
Explanation: There are no lists, so the merged result is empty.
Constraints:
- 0 ≤ k ≤ 500
- 0 ≤ length of each list ≤ 500
- The total number of values across all lists is at most 10⁴
- -10⁴ ≤ node value ≤ 10⁴
- Every input list is sorted in non-decreasing order.
Hints:
Merging everything into one pile and sorting works — but it ignores that each list is already sorted. What did the two-list merge exploit?
At any moment the next output value must be one of the k front nodes. A min-heap keyed on those k fronts finds the smallest in O(log k) instead of O(k).
Alternatively, merge the lists in pairs — k lists become k/2, then k/4, … Each value is touched once per round and there are only log k rounds.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Expected output: [1, 1, 2, 3, 4, 4, 5, 6]