Merge k sorted lists
Several sorted linked lists need to become one. The list lists holds k linked lists, and the values in each one run from smallest to largest. Combine them into a single linked list that holds every value, also running from smallest to largest with every repeated value kept, and return its head. When there are no nodes at all, return None.
A linked list is a chain of ListNode objects. Each node has a value val and a pointer next to the following node, and the last node's next is None. A linked list is passed around as its first node, its head, and an empty linked list is None. You may reuse the nodes you are given.
The examples write each linked list as the list of its values.
lists = [[2, 6, 9], [1, 7], [3, 4, 8]]Output[1, 2, 3, 4, 6, 7, 8, 9]Each step takes the smallest value at the front of any list: 1 from the second list, then 2 from the first, then 3 from the third, and so on.
lists = [[], [5, 5], []]Output[5, 5]Empty lists add nothing, and both 5s stay.
lists = []Output[]No lists at all, so the result is empty: return None.
0 ≤ k = len(lists) ≤ 104
Each linked list has 0 to 500 nodes and is sorted from smallest to largest.
At most 105 nodes in total.
-105 ≤ val ≤ 105
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.