Heaps Merging k sorted lists
421. Merge k Sorted Lists
You are given an array lists of k singly linked lists. Each list is sorted in non-decreasing order. Merge
all of them into one list sorted in non-decreasing order, made of the nodes of the given lists, and return
its head.
Non-decreasing order means each value is at least the one before it, so equal values can sit next to each other. The answer keeps every node, duplicates included. Any list can be empty, and an empty list is a null head. If there are no nodes at all, return null.
The examples write each list as its values from the head on, so lists = [[1,4],[2]] holds the two lists
1 → 4 and 2. The output shows the list you return the same way, and an empty list as [].
Example 1
Input: lists = [[2, 6, 9], [1, 6, 10, 14], [3, 4]]
[1,2,3,4,6,6,9,10,14]Explanation: The answer holds all nine nodes in order. The two 6s come from different lists, and both are kept.
Example 2
Input: lists = [[], [-5, -5, 0], [], [7]]
[-5,-5,0,7]Explanation: Two of the four lists are empty. They add nothing, and the other two are merged as usual.
Example 3
Input: lists = []
[]Explanation: There are no lists, so there are no nodes, and the answer is null.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ k ≤ 105, where k islists.length0 ≤ total number of nodes ≤ 105-109 ≤ Node.val ≤ 109- Each list is sorted in non-decreasing order.
Clarifying questions
What you would ask an interviewer before writing any code.