LeetCode 23 Hard，K个链表归并
- 2020 年 3 月 5 日
- 筆記
链接
https://leetcode.com/problems/merge-k-sorted-lists/
难度
Hard
描述
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
给定K个有序链表，要求将它所有的元素归并到一个链表，并且有序。
样例:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1- >1->2->3->4->4->5->6
题解
按照惯例，我们还是先来看最简单的解法，也就是暴力法。
暴力
这题当中，暴力的方法也很简单，非常简单粗暴，那就是先把所有元素取出来，排序之后再放到链表当中去。但是这么做说实话有点脱裤子放屁，我们分析一下复杂度也会发现，假设所有的元素个数是n，那么最后的复杂度应该就是排序所消耗的复杂度，也就是，和K没有一点关系，而且我们也完全没有用上这K个链表当中的元素都是有序的这个信息，显然这是不科学的。
我们对上面的纯暴力方法稍稍做一些优化，想办法把K个链表当中元素有序的信息用上。用上的方法也很简单，我们之前做归并排序的时候曾经做过两个数组的归并，我们用同样的方法，只不过我们这次换成是K个链表而已。也就是说我们每次遍历这K个链表的头元素，从其中取出最小的那个元素插入最后的结果链表当中，当所有链表为空的时候，说明所有的元素已经归并完了，那么进行返回。
我们来试着写一下代码：
class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: import sys ret = ListNode(0) pnt = ret while True: mini = sys.maxsize node = None # 遍历所有的链表 for i, l in enumerate(lists): if l is None: continue if l.val < mini: mini = l.val node = i # 如果node为None，说明所有的元素都已经归并结束了 if node is None: break pnt.next = ListNode(mini) pnt = pnt.next lists[node] = lists[node].next return ret.next
这种算法的复杂度是多少呢？稍微算一下就知道，我们每一次选择数的时候，都需要遍历K个链表的头指针。一共有n个元素，所以总体的复杂度是。和之前暴力的方法相比如何呢？其实是半斤八两，这两者谁大谁小完全取决于K和的大小关系。一般来说n不会超过一千万，所以不会很大，粗略估算，不会超过30，而K很有可能超过30。也就是说大部分情况下这种方法的运算时间要比暴力还要长。
看起来这个用上了链表内元素大小关系浓眉大眼的归并法，还不如之前简单粗暴的暴力来得管用。实在是有点粉刺。
归并
我们回想一下从前，在之前的问题当中，我们遇到比较多的往往是两个数组的归并，这次是K个链表，因此复杂度增加了许多。那么我们能不能把这K个链表看成是两两链表的组合呢？我们每次将这些链表两两分组，然后归并之后再次两两分组归并，直到最后只剩下一个链表为止，这种方案会不会更优一些呢？
我们画张图来看看这一过程：
我们横向来看，在每一次merging阶段当中，我们都遍历了全部的元素，所以每一层总体的复杂度是。那么，我们一共又遍历了多少层呢？也不难，我们每次merging，链表的数量都会减少一半。一共有K个链表，那么显然，应该要merging 次，也就是说有个merging阶段，所以总体的复杂度是。由于K不会太大，所以这种方法显然要优于和.
我们先来写出两个链表归并的代码，之后再递归的形式调用即可：
class Solution: def mergeTwoList(self, l1, l2): ret = ListNode(0) pnt = ret while True: """ 链表没办法像数组那样在末尾插入标兵了 所以只能人工判断是否为空的情况 """ if l1 is None and l2 is None: break if l1 is None: pnt.next = ListNode(l2.val) pnt = pnt.next l2 = l2.next elif l2 is None: pnt.next = ListNode(l1.val) pnt = pnt.next l1 = l1.next else: if l1.val < l2.val: pnt.next = ListNode(l1.val) l1 = l1.next else: pnt.next = ListNode(l2.val) l2 = l2.next pnt = pnt.next return ret.next def dfs(self, lists, l, r): """ 递归合并K个链表 这里的l和r维护的是闭区间 """ if l > r: return None if l == r: return lists[l] else: mid = (l + r) // 2 return self.mergeTwoList(self.dfs(lists, l, mid), self.dfs(lists, mid+1, r)) def mergeKLists(self, lists: List[ListNode]) -> ListNode: # 传入l=0， r=len(lists)-1，因为是闭区间 return self.dfs(lists, 0, len(lists)-1)
优先队列
到这里还没有结束，下面要介绍的是可以说是我个人觉得这题最棒的解法了，就是使用我们之前说的优先队列。还记得吗，优先队列可以自动保证队列当中的元素有序。只要利用优先队列，然后将当前第一个元素作为优先级，让优先队列帮我们维护队列当中的顺序。通过使用优先队列，我们的代码无论是可读性还是编码复杂度都会大大降低。
如果有新关注的，或者是已经遗忘了优先队列用法的同学可以点击下方链接，回顾一下优先队列的用法：Python应用——优先队列与heapq
class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: class Node: """ 存储在优先队列当中的节点 """ def __init__(self, val, arr): self.val = val self.arr = arr # 重载判断大小的比较函数 def __lt__(self, other): return self.val < other.val import heapq arr = [] # 将所有链表插入优先队列当中 for l in lists: if l is not None: heapq.heappush(arr, Node(l.val, l.next)) ret = ListNode(0) pnt = ret while len(arr) > 0: # 从优先队列头部获取元素，需要注意，pop之后元素会从队列中删除 node = heapq.heappop(arr) val, l = node.val, node.arr pnt.next = ListNode(val) pnt = pnt.next # 获取完头部元素之后，将剩下的链表插入回队列当中 if l is not None: heapq.heappush(arr, Node(l.val, l.next)) return ret.next
这种方法从代码复杂度上要比上一种要小很多，但是我们来分析一下会发现，对于优先队列而言，每次插入的复杂度是，由于我们一共有K个链表，所以插入的复杂度是，一共有n个元素，所以最终的复杂度依然是和归并的方法是一样的。但是数据结构的使用简化了我们计算的过程，这也是我们之所以学习各种数据结构的原因和意义。
今天这道题呢虽然挂的难度是Hard，但其实并不难，哪怕是我们暴力求解都可以通过。因此希望大家不要被它上面写的难度所吓到，另外，这题对于优先队列的应用也非常经典，非常值得学习。
今天的文章就是这些，如果觉得有所收获，请顺手点个在看或者转发吧，你们的举手之劳对我来说很重要。
