合并K个有序链表(分治+递归)(python版）

首先吐槽一下，有些老铁采用了这种投机取巧的方法：直接遍历列表，取出每个链表里面的值然后进行数组排序，最后再依次插入到一个新链表中。

喂，你要这么写，那面试官只能面带微笑的告诉你：“写的不错，今天的面试就先到这里吧。”
很明显这种解法走偏了，自己刷题可以试，面试可别这么整。这种题其实就是两个有序链表合并的升级版。下面讲下思路：

思路：
这道题目最容易想到的做法是，使用【合并两个有序链表】中的方法，融合前两个链表，将下一个链表与当前结果融合，遍历列表中的每个链表，不断循环下去。但是这种方法时间复杂度很高，我们考虑用二分法把列表进行中间拆分，将列表都拆成长度相等的两个列表，然后融合每个小列表中的链表即可。这样就可以将K级别的融合计算量转换为log(K)级别。

代码（分治递归法）

# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class ListNode:
     def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self , lists ):
        if len(lists) <= 2: 
            return self.mergeTwoLists(lists)

        def splitLists(lists):
            idx = len(lists) // 2
            return lists[:idx], lists[idx:]
        a, b = splitLists(lists)
        a_merge = self.mergeKLists(a)
        b_merge = self.mergeKLists(b)
        return self.mergeTwoLists([a_merge, b_merge])

    def mergeTwoLists(self, lists):
            if not lists: return None
            if len(lists)==1: return lists[0]
            head1, head2 = lists
            head = dump = ListNode(0)
            while head1 and head2:
                if head1.val < head2.val:
                    head.next = head1
                    head1 = head1.next
                else:
                    head.next = head2
                    head2 = head2.next
                head = head.next
            head.next = head1 if head1 else head2
            return dump.next

当然有的铁子们说，我还可以用优先队列来实现呀！
没毛病，老铁，但复杂度稍微高点，而且需要import对应的库，虽不建议，但练练手实现一下也无妨嘛，来简单看一下吧。

思路
主要是利用最小堆方法，用一个大小为K的最小堆（用优先队列+自定义降序实现）(优先队列就是大顶堆，队头元素最大,自定义为降序后，就变成小顶堆，队头元素最小)，先把K个链表的头结点放入堆中，每次取堆顶元素，然后将堆顶元素所在链表的下一个结点加入堆中。

代码（优先队列）

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        dump= ListNode(0)
        p = dump
        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 dump.next

麻豆出品，必出精品！