1753

#heap
#lt

Wow in #leetcode we can #patch classes:

ListNode.__lt__ = lambda self, other: self.val < other.val

This is good for simpler support of heap - by providing the object only - without the index and value.

Full:

import heapq

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

ListNode.__lt__ = lambda self, other: self.val < other.val

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []

        for node in lists:
            if node:
                heapq.heappush(heap, node)

        head: List[ListNode] = ListNode()
        tail = head

        while heap:
            node = heapq.heappop(heap)
            tail.next = node
            tail = node

            if node.next:
                heapq.heappush(heap, node.next)

        return head.next

23. Merge k Sorted Lists

👍 1