Merge K Sorted Linked Lists
Problem statement
Merge all the sorted singly linked lists into one nondecreasing linked list. Return its head, retaining every original node exactly once, including duplicate values.
Relink existing nodes without changing their values. You may update the input head array and use a dummy node that is not returned. Inputs and outputs are serialized as value arrays; an empty array represents an empty linked list. The outer input array contains the individual lists.
Function
mergeKLists(lists: ListNode[]) → ListNodeExamples
Example 1
lists = [[0,4],[1,3],[2,5]]return = [0,1,2,3,4,5]Interleaving the three sorted chains gives [0,1,2,3,4,5]; all six original nodes remain in the result.
Example 2
lists = [[],[-2,7],[]]return = [-2,7]Only the middle list has nodes, so the result is [-2,7].
Constraints
0 <= lists.length <= 100 <= lists[i].length <= 50-1000000 <= lists[i][j] <= 1000000- Every input list is sorted in nondecreasing order, acyclic, and disjoint from the other input lists.