LeetCode 23: Merge k Sorted Lists

Sweep line

With the list heads in a min-heap, we can traverse them in sorted order using sweep line.

If we have a tuple like $(a, b)$ in the heapq, the primary key is $a$ and the secondary key is $b$ . The primary keys are compared using strictly-less-than operator. If there is a tie, the comparison is done using the secondary key. To get around this nuance, we use ListHead having comparison using $\le$ .

Say there are $n$ linked lists and the longest list have $m$ nodes.

Time: $\mathcal{O}(n \cdot m \cdot \lg{n})$ , space: $\mathcal{O}(n)$ .

from heapq import heapify, heappush as push, heappop as pop


class ListHead:
    def __init__(self, head):
        self.node = head

    def has_next(self):
        return bool(self.node.next)

    def next(self):
        return ListHead(self.node.next)

    def __lt__(self, other):
        return self.node.val <= other.node.val


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:

        min_heap = [ListHead(head) for head in lists if head]
        heapify(min_heap)

        dummy = ListNode()
        t = dummy
        while min_heap:
            list_head = pop(min_heap)
            t.next = list_head.node
            t = t.next

            if list_head.has_next():
                push(min_heap, list_head.next())

        return dummy.next

unreasonably effective