合并k个已排序的链表

合并k个已排序的链表_牛客题霸_牛客网

问题简述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

思路：堆/优先队列

写法1：不重载运算符，利用 tuple 排序

class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        
        import heapq
        
        h = []
        cnt = 0  # 一个自增变量，避免直接对 node 排序
        
        # init
        for node in lists:
            if node:
                heapq.heappush(h, (node.val, cnt, node))
                cnt += 1
        
        cur = dummy = ListNode(0)
        while h:
            _, _, node = heapq.heappop(h)
            cur.next = node
            cur = cur.next
            if node.next:
                node = node.next
                heapq.heappush(h, (node.val, cnt, node))
                cnt += 1
        
        return dummy.next

写法2：重载运算符

class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        
        import heapq
        
        h = []
        cnt = 0
        
        # 重载运算符
        def lt(a, b):
            return a.val < b.val
        ListNode.__lt__ = lt

        # 下面的写法也可以，但是不推荐，因为 lambda 表达式是不支持序列化的
        # ListNode.__lt__ = lambda a, b: a.val < b.val
        
        # init
        for node in lists:
            if node:
                heapq.heappush(h, node)
        
        cur = dummy = ListNode(0)
        while h:
            node = heapq.heappop(h)
            cur.next = node
            cur = cur.next
            if node.next:
                node = node.next
                heapq.heappush(h, node)
        
        return dummy.next