本文共 2331 字，大约阅读时间需要 7 分钟。

题目：合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。（困难）

输入:[  1->4->5,  1->3->4,  2->6]输出: 1->1->2->3->4->4->5->6

方法一：顺序合并（略）

方法二：分治合并（略） 方法三：最小堆（优先队列）： heapq模块： python最小堆heapq有两种方式创建堆， 一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中，另外一种就是使用heap.heapify(list)转换列表成为堆结构。 相关函数：

• heapq.heappop() 函数弹出堆中最小值
• heapq.heaprepalce() 删除堆中最小元素并加入一个元素
• heapq.nlargest() 或 heapq.nsmallest() 获取堆中最大或最小的范围值

PriorityQueue模块：

含有一个属性queue,输出队列中每个元素，三个方法，分别是qsize()，代表优先级队列中元素个数，put()，用heappush()方法将元素放入队列，get()，用heappop()方法将元素从队列取出。 注意事项：

• 元组在heapq里比较的机制是从元组首位0开始，即遇到相同，就比较元组下一位，比如(1,2), (1,3)，前者比后者小。
• 利用python自带heapq实现最小堆的时候，直接把（node.value,node)组成元组放进队列里，结果leetcode编译器报错,显示<无法对LISTNode类型数据进行操作，因为node是不可比较对象
• 两种解决方法：

（1）重写ListNode类，使得ListNode对象可以比较：

class Solution:    def mergeKLists(self, lists: List[ListNode]) -> ListNode:        from queue import PriorityQueue        class PQ(object):            def __init__(self, node):                self.node = node                self.val = node.val            def __lt__(self, other):                return self.val < other.val# Python中基类object提供了一系列可以用于实现同类对象进行“比较”的方法，可以用于同类对象的不同实例进行比较，包括__lt__、__gt__等方法                q = PriorityQueue()        for node in lists:            if node != None:                q.put(PQ(node))        head = ListNode(0)        tail = head        while not q.empty():            tmp = q.get().node            new_node = tmp.next            if new_node != None:                q.put(PQ(new_node))            tmp.next = None            tail.next = tmp            tail = tail.next        return head.next

（2）往最小堆中添加元组时，增加一项下标，当节点值相同时，可以比较下标大小，避免了比较节点大小：heapq.heappush(h, (listnode.val, index, listnode))

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def mergeKLists(self, lists: List[ListNode]) -> ListNode:        import heapq        dummy = ListNode(0)        node = dummy        h = []        for i, listnode in enumerate(lists):            if listnode != None:                heapq.heappush(h, (listnode.val, i, listnode))        while h:            val, i, listnode = heapq.heappop(h)            node.next = listnode            node = node.next            listnode = listnode.next            if listnode:                heapq.heappush(h, (listnode.val, i, listnode))        return dummy.next

转载地址：http://uexoz.baihongyu.com/