Write merge_k_lists(lists). lists is a Python list of linked-list heads (ListNode or None), each sorted in non-decreasing order. Return the head of a single sorted linked list made by splicing together all the original nodes (don't allocate new value nodes; a dummy head is fine).
lists = [ 1 -> 5 -> 6, 2 -> 3, None, 0 -> 5 ]
result: 0 -> 1 -> 2 -> 3 -> 5 -> 5 -> 6
lists = [] result: None
lists = [None] result: None
Up to 40,000 lists and 120,000 nodes.
⭐ Bonus: a speed test with 2,000 lists earns a star in O(N log k) (N total nodes). Merging the lists into an accumulator one at a time is O(N·k).
Show hint
At every step the next output node is the smallest of the k current fronts. Keep the fronts in a structure that finds and replaces the smallest in O(log k). ListNode objects can't be compared, so give ties something comparable to fall back on.