Merge K Sorted Lists

You are given an array of k linked lists lists, where each list is sorted in ascending order.

Return the sorted linked list that is the result of merging all of the individual linked lists.

Approach

Use a min-heap to always select the smallest current head among the k lists. Push each non-null list head into the heap, then repeatedly pop the smallest node, append it to the result, and push its next node. This handles empty lists and duplicates naturally.

Why It Works

At any time, the heap contains the smallest remaining node from each list. The smallest among them must be the next node in the merged order. By pushing the popped node's successor, the heap continues to represent the current list heads, producing a fully sorted merge.

Complexity

• Time: O(N log k) where N is the total number of nodes
• Space: O(k)

Reference Implementation (Python)

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        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 = tail.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next