↓Skip to main content
  1. Posts/

LeetCode-23 合并 K 个升序链表

·1 min·
Table of Contents

LeetCode-23 合并 K 个升序链表 #

Solution 1 #

用最小堆保证每次取出的节点的值最小.

代码如下:

ListNode.__lt__ = lambda a, b: a.val < b.val
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        pq = []
        dummy = ListNode()
        p = dummy
        for head in lists:
            if head:
                heappush(pq, head)
        while pq:
            node = heappop(pq)
            p.next = node
            p = p.next
            if node.next:
                heappush(pq,node.next)
        return dummy.next