You are given an array lists of k sorted linked lists — written [[1,4,5],[1,3,4],[2,6]] in the tests. Merge them all into one sorted list and return its head. The array may be empty, and it may contain empty lists.
Examples
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Example 4:
Input: lists = [[7]]
Output: [7]
Constraints
0 <= k <= 10^4
0 <= each list's length <= 500
-10^4 <= Node.val <= 10^4
Every list is sorted ascending.
Prerequisites
Linked lists — a node holds a value and a next reference, and rearranging a list means moving references, never values. Dummy heads: a node in front of the list so the first element stops being a special case. Two pointers on a list — one ahead of the other, or one moving twice as fast.
How to think about it
1. Min-Heap of the Fronts Optimal
Intuition
The next node of the answer is the smallest front among the k lists — and "smallest of k, repeatedly" is what a heap is for. Every node enters and leaves the heap once, so the cost is one log-k comparison per node rather than a scan of all k. Merging the lists one at a time re-walks the accumulated result each round, which is the O(N*k) answer this replaces.
Algorithm
1. Push the head of every non-empty list into a min-heap keyed on value. 2. Pop the smallest, attach it to the tail of the answer. 3. Push that node's successor, if any. 4. Repeat until the heap empties.
Time & Space
Time O(N log k) for N nodes across k lists. Space O(k) for the heap. Divide-and-conquer pairwise merging reaches the same bound.