Merge k Sorted Lists

Problem

Given an array of k linked lists, each sorted in ascending order, merge them all into one sorted linked list and return it.

Approach

Keep a min-heap holding the current head of each list. The smallest of those heads is the next node of the merged list.

Pop the smallest node, attach it to the result, and push that node's successor if it has one. Repeat until the heap is empty.

Store the list index alongside each value in the heap. When two values tie, Python compares the next tuple element, and the index stops it from trying to compare two list nodes.

Solution

import heapq


class Solution:
    def mergeKLists(self, lists: list[ListNode | None]) -> ListNode | None:
        heap = []
        for index, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, index, node))

        dummy = tail = ListNode()
        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

Complexity

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

Edge cases

• An empty array or a list of empty lists returns None.
• A single list is returned unchanged.
• Merging the lists in pairs is an alternative with the same O(N log k) time.