Merge k Sorted Lists

Intuition

Because each of the k input lists is already sorted, the smallest unused element across all lists is always sitting at one of the current list heads. A min-heap lets us fetch that global minimum in O(log k) time instead of rescanning all k heads every step. We seed the heap with every non-empty head, then repeatedly pop the smallest node, append it to the output, and push its successor if one exists. This keeps the heap size bounded by k while we drain all N nodes. An alternative is divide-and-conquer: pair up the lists and merge them two at a time, halving the count of lists each round, which reaches the same O(N log k) time without an explicit heap.

Algorithm walkthrough

1. 1Create a dummy head with a tail pointer, and push the head node of every non-empty list into a min-heap ordered by node value.
2. 2Pop the node holding the smallest value from the heap.
3. 3Append that node to the tail of the output list and advance the tail pointer.
4. 4If the popped node has a next node, push that successor into the heap.
5. 5Repeat until the heap is empty.
6. 6Return dummy.next, which is the head of the fully merged list.

Implementation

import heapq

class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        heap = []
        # Use the list index as a tie-breaker so nodes are never compared directly.
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

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