lists holds k linked lists, and each of them is already sorted from smallest to largest. Combine all of their nodes into a single sorted linked list and return its head.
The smallest head is 1, from lists[1], so it comes first. Then 2 from lists[0], then 3 and 4 from lists[2], and so on. Both 6s stay in the result.
Empty lists add nothing. The single node -5 goes in front of everything else.
Two empty lists merge into an empty list.
Constraints
k == lists.length0 <= k <= 10⁴0 <= lists[i].length <= 500-10⁴ <= lists[i][j] <= 10⁴lists[i] is sorted in non-decreasing order.10⁴ nodes.The next node of the merged list is always the smallest of the k current heads. Find that quickly, and you never need to look past the front of any list.
Ask which node comes first in the answer. Every list is sorted, so each list's smallest node is its front node. The smallest node overall is therefore the smallest of the k front nodes. Nothing deeper in any list can beat it.
Time O(k + N log k)Space O(k)
The full walkthrough and code are part of Premium
[[2,6,9],[1,6],[3,4,10]]