78. Merge K sorted Lists
Given heads of k sorted linked lists as an array called heads, merge them into one single sorted linked list and return the head of that list.
Example 1:
Input: heads = [[head -> 1 -> 2 -> 3 -> 4], [head -> -4 -> -3], [head -> -5 -> -3 -> 1 -> 2 -> 3 -> 4]]
Output: head -> -5 -> -4 -> -3 -> -3 -> 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4
Explanation:
head -> -5 -> -4 -> -3 -> -3 -> 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4
The nodes in bold come from the 3rd list, the underlined nodes come from the 2nd list, rest are from the 1st list.
Example 2:
Input: heads = [[head -> -5 -> -4 -> -1], [head -> 10 -> 11 -> 12]]
Output: head -> -5 -> -4 -> -1 -> 10 -> 11 -> 12
Explanation:
head -> -5 -> -4 -> -1 -> 10 -> 11 -> 12
The nodes in bold come from the 1st list, rest are from the 2nd list.
Now Your Turn!
Pick the correct output for the given inputInput: heads = [[head -> 10 -> 12], [head -> 10 -> 12], [head -> 10 -> 10 -> 12]]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 2 <= k <= 100
- 1 <= number of nodes in each list <= 100
- -1000 <= values of each node <= 1000
- All lists are sorted in non-decreasing order.