LeetCode 23 Hard，K个链表归并

本文始发于个人公众号：TechFlow，原创不易，求个关注

链接

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，那么最后的复杂度应该就是排序所消耗的复杂度，也就是 $O(nlogn)$ ，和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个元素，所以总体的复杂度是 $O(nk)$ 。和之前暴力的方法 $O(nlogn)$ 相比如何呢？其实是半斤八两，这两者谁大谁小完全取决于K和 $logn$ 的大小关系。一般来说n不会超过一千万，所以 $logn$ 不会很大，粗略估算，不会超过30，而K很有可能超过30。也就是说大部分情况下这种方法的运算时间要比暴力还要长。

看起来这个用上了链表内元素大小关系浓眉大眼的归并法，还不如之前简单粗暴的暴力来得管用。实在是有点粉刺。

归并

我们回想一下从前，在之前的问题当中，我们遇到比较多的往往是两个数组的归并，这次是K个链表，因此复杂度增加了许多。那么我们能不能把这K个链表看成是两两链表的组合呢？我们每次将这些链表两两分组，然后归并之后再次两两分组归并，直到最后只剩下一个链表为止，这种方案会不会更优一些呢？

我们画张图来看看这一过程：

我们横向来看，在每一次merging阶段当中，我们都遍历了全部的元素，所以每一层总体的复杂度是 $O(n)$ 。那么，我们一共又遍历了多少层呢？也不难，我们每次merging，链表的数量都会减少一半。一共有K个链表，那么显然，应该要merging $logK$ 次，也就是说有 $logK$ 个merging阶段，所以总体的复杂度是 $nlogK$ 。由于K不会太大，所以这种方法显然要优于 $nlogn$ 和 $nK$ .

我们先来写出两个链表归并的代码，之后再递归的形式调用即可：

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

这种方法从代码复杂度上要比上一种要小很多，但是我们来分析一下会发现，对于优先队列而言，每次插入的复杂度是 $logn$ ，由于我们一共有K个链表，所以插入的复杂度是 $logK$ ，一共有n个元素，所以最终的复杂度依然是 $nlogK$ 和归并的方法是一样的。但是数据结构的使用简化了我们计算的过程，这也是我们之所以学习各种数据结构的原因和意义。

今天这道题呢虽然挂的难度是Hard，但其实并不难，哪怕是我们暴力求解都可以通过。因此希望大家不要被它上面写的难度所吓到，另外，这题对于优先队列的应用也非常经典，非常值得学习。

今天的文章就是这些，如果觉得有所收获，请顺手扫码点个关注吧，你们的举手之劳对我来说很重要。