Description
Merge k ascending linked lists into one ascending list by relinking nodes.
Solution
from heapq import heappush, heappop
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heappush(heap, (node.val, i, node))
dummy = tail = ListNode()
while heap:
_, i, node = heappop(heap)
tail.next = node
tail = node
if node.next:
heappush(heap, (node.next.val, i, node.next))
return dummy.nextExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[1,4],[2,5],[3]]]- Output
[1,2,3,4,5]
The smallest available head is taken at every step.
Example 2
- Input
[[]]- Output
[]
There are no lists.
Example 3
- Input
[[[],[2]]]- Output
[2]
Empty lists do not contribute nodes.
Approach
Maintain a min-heap of current list heads, replacing each popped head with its successor.
Time & space
O(N log(k + 1)) time; O(k) space for N total nodes.