题目23：合并K个排序链表思路1：如何把所有节点放进 r(result link)？怎么对 r 排序？如何修改每个节点的指针？==代码实现== 思路2：知识点补充-Python heapq（堆操作）用法详解优先级队列==代码实现== 思路3：分而治之==代码实现==

题目23：合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

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

思路1：

把题目给的所有链表中的所有节点放进一个列表 r。对这个列表 r 中的所有节点进行从大到小的排序。O(NlogN)把每个节点的指针指向前一个节点。（第一个节点，也就是最大的那个，指向None。）返回最后一个节点，也就是整个新链表的开头。

如何把所有节点放进 r(result link)？

我们首先初始化 r 为空列表，初始化 n(node) 为题目所给的第一个链表的开头节点，并删除lists中的这个节点，接着进入while循环，如果 n 不为空，那么 r += [n]，这里使用了切片的技巧（$r[len(r):]=[n]$相当于r=r+[n]），n=n.next，如果n是第一个链表的最后一个节点的话n.next就是None，下一次while的时候如果lists不为空就说明还有别的链表，此时n为None，我们让 r 不变，n=lists.pop()，也就是从lists中再取下一个节点赋值给n，重复以上步骤直到 lists 为空，我们就把所有节点放进 r 了。

怎么对 r 排序？

用了sorted函数，其中key定义了排序时用来比较的是每个元素的val属性，同时设置reverse为True代表降序排序。

如何修改每个节点的指针？

我们初始化 p(previous node) 为None。遍历降序排好的列表 r，r中的第一个元素就是值最大的元素，也就是我们应该返回的链表的结尾，我们设置它指向None，然后让p=这个节点，继续for循环。之后每经过一个节点 n 就把这个节点的next属性设置为上一个节点 p，遍历完成之后的 n，也就是我们遍历经过的最后一个元素，拥有最小的值，自然就是整个新链表的起始节点，我们将其作为输出值，函数返回。

代码实现

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: r, n, p = [], lists and lists.pop(), None while lists or n: r[len(r):], n = ([n], n.next or lists and lists.pop()) if n else ([], lists.pop()) for n in sorted(r, key=lambda x: x.val, reverse=True): n.next, p = p, n return n if r else []

思路2：

知识点补充-Python heapq（堆操作）用法详解

Python heapq（堆操作）用法详解 http://c.biancheng.net/view/2432.html

Python 并没有提供“堆”这种数据类型，它是直接把列表当成堆处理的。Python 提供的 heapq 包中有一些函数，当程序用这些函数来操作列表时，该列表就会表现出“堆”的行为。

在交互式解释器中先导入 heapq 包，然后输入 heapq.__all__ 命令来查看 heapq 包下的全部函数，可以看到如下输出结果： >>> heapq.__all__ ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']

上面这些函数就是执行堆操作的工具函数，这些函数的功能大致如下： ● heappush(heap, item)：将 item 元素加入堆。 ● heappop(heap)：将堆中最小元素弹出。 ● heapify(heap)：将堆属性应用到列表上。 ● heapreplace(heap, x)：将堆中最小元素弹出，并将元素x 入堆。 ● merge(*iterables, key=None, reverse=False)：将多个有序的堆合并成一个大的有序堆，然后再输出。 ● heappushpop(heap, item)：将item 入堆，然后弹出并返回堆中最小的元素。 ● nlargest(n, iterable, key=None)：返回堆中最大的 n 个元素。 ● nsmallest(n, iterable, key=None)：返回堆中最小的 n 个元素。

下面程序示范了这些函数的用法：

from heapq import * my_data = list(range(10)) my_data.append(0.5) # 此时my_data依然是一个list列表 print('my_data的元素：', my_data) # 对my_data应用堆属性 heapify(my_data) print('应用堆之后my_data的元素：', my_data) heappush(my_data, 7.2) print('添加7.2之后my_data的元素：', my_data)

上面程序开始创建了一个 list 列表，接下来程序调用 heapify() 函数对列表执行堆操作，执行之后看到 my_data 的元素顺序如下：

应用堆之后my_data 的元素：[0 , 0.5, 2, 3, 1, 5, 6, 7, 8, 9, 4]

这些元素看上去是杂乱无序的，但其实并不是，它完全满足小顶堆的特征。我们将它转换为完全二叉树，可以看到如图 2 所示的效果。

图 2 小顶堆对应的完全二叉树

当程序再次调用 heappush(my_data, 7.2) 向堆中加入一个元素之后，输出该堆中元素，可以看到如下输出结果：

添加7.2 之后my_data 的元素：[0, 0.5, 2, 3, 1, 5, 6, 7, 8, 9, 4,7.2]

此时将它转换为完全二叉树，可以看到如图 3 所示的效果。 图 3 添加 7.2 之后的小顶堆对应的完全二叉树

接下来程序尝试从堆中弹出两个元素：

# 弹出堆中最小的元素 print(heappop(my_data)) # 0 print(heappop(my_data)) # 0.5 print('弹出两个元素之后my_data的元素：', my_data)

上面三行代码的输出如下：

0 0.5 弹出两个元素之后my_data的元素： [1, 3, 2, 7, 4, 5, 6, 7.2, 8, 9]

从最后输出的 my_data 的元素来看，此时 my_data 的元素依然满足小顶堆的特征。

下面代码示范了 replace() 函数的用法：

# 弹出最小元素，压入指定元素 print(heapreplace(my_data, 8.1)) print('执行replace之后my_data的元素：', my_data)

执行上面两行代码，可以看到如下输出结果：

1 执行replace之后my_data的元素： [2, 3, 5, 7, 4, 8.1, 6, 7.2, 8, 9]

也可以测试通过 nlargest()、nsmallest() 来获取最大、最小的 n 个元素，代码如下：

print('my_data中最大的3个元素：', nlargest(3, my_data)) print('my_data中最小的4个元素：', nsmallest(4, my_data))

运行上面程序，可以看到如下输出结果：

my_data中最大的3个元素： [9, 8.1, 8] my_data中最小的4个元素： [2, 3, 4, 5]

通过上面程序不难看出，Python 的 heapq 包中提供的函数，其实就是提供对排序算法中“堆排序”的支持。Python 通过在底层构建小顶堆，从而对容器中的元素进行排序，以便程序能快速地获取最小、最大的元素，因此使用起来非常方便。

优先级队列

时间复杂度：$O(n\ast log(k))$，n 是所有链表中元素的总和，k 是链表个数。

代码实现

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: import heapq dummy = ListNode(0) p = dummy head = [] for i in range(len(lists)): if lists[i] : heapq.heappush(head, (lists[i].val, i)) lists[i] = lists[i].next while head: val, idx = heapq.heappop(head) p.next = ListNode(val) p = p.next if lists[idx]: heapq.heappush(head, (lists[idx].val, idx)) lists[idx] = lists[idx].next return dummy.next

思路3：

分而治之

链表两两合并

代码实现

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: if not lists:return n = len(lists) return self.merge(lists, 0, n-1) def merge(self,lists, left, right): if left == right: return lists[left] mid = left + (right - left) // 2 l1 = self.merge(lists, left, mid) l2 = self.merge(lists, mid+1, right) return self.mergeTwoLists(l1, l2) def mergeTwoLists(self,l1, l2): if not l1:return l2 if not l2:return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2