D
At Meta, imagine multiple pre-sorted event streams need to be combined into one ordered feed. Given k sorted singly linked lists, merge them into one sorted linked list and return its head.
Implement a function that takes lists, where lists[i] is the head of a sorted singly linked list or null. Each node contains an integer value and a next pointer. Return the head of a new merged sorted linked list formed by reusing the existing nodes.
Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: Repeatedly taking the smallest current node across the three lists produces the fully sorted merged list.
Example 2
Input: lists = []
Output: []
Explanation: There are no lists to merge, so the result is empty.
Example 3
Input: lists = [[]]
Output: []
Explanation: The only list is empty.
0 <= k <= 10^40 <= total number of nodes <= 10^5-10^4 <= Node.val <= 10^4Aim for a solution better than collecting all values and sorting them again.
lists = [[1,4,5],[1,3,4],[2,6]]Output[1,1,2,3,4,4,5,6]WhyAt each step, choose the smallest current head among the three lists until all nodes are consumed.lists = []Output[]WhyNo input lists means there is nothing to merge.lists = [[]]Output[]WhyThe single list is empty, so the merged result is also empty.0 <= k <= 10^40 <= total number of nodes <= 10^5-10^4 <= Node.val <= 10^4Each linked list is sorted in non-decreasing orderdef merge_k_lists(lists):