Merge K Sorted Lists

Merge many sorted linked lists into one sorted list.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Merge K Sorted Lists: A min-heap containing one current head per nonempty list always exposes the globally smallest unmerged node.

Input and goalMerge many sorted linked lists into one sorted list.

Seed one head from each listPush tuples (1,0,A1), (1,1,B1), and (2,2,C2). The list index breaks the value-1 tie, so A1 is the root.

candidate min-heap

• (1,0,A1)
  • (1,1,B1)
  • (2,2,C2)

inputListsA:1->4->5; B:1->3->4; C:2->6heapArray[(1,0,A1),(1,1,B1),(2,2,C2)]taildummyoutputOrder[]

Recognize it

Use it when k individually sorted streams must be merged and only their current heads can be candidates for the next global minimum.

Keep true

The heap contains exactly the first unmerged node of each nonexhausted list, and the tail follows all nodes already popped in nondecreasing tuple order.

Reuse it

For sorted sources, keep only one frontier item per source and replace it from the same source after extraction. The pattern transfers to external merge, log aggregation, and k-way iterators.

Pattern: Heap with one current node from each list.

Simple idea: The next result node must be the smallest current head. The heap finds that node. After removing it, add the next node from the same list.

import heapq

def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
   heap: list[tuple[int, int, ListNode]] = []
   for index, node in enumerate(lists):
      if node:
         heapq.heappush(heap, (node.val, index, node))

   dummy = ListNode(0)
   tail = dummy
   while heap:
      _, index, node = heapq.heappop(heap)
      tail.next = node
      tail = node
      if node.next:
         heapq.heappush(heap, (node.next.val, index, node.next))
   return dummy.next

Cost: $O(n\log k)$ time and $O(k)$ space, where $n$ is the total node count.

The platform supplies ListNode with val and next; this snippet assumes that definition.