Leetcode-talk12合并K个排序链表

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

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

法一：分治法
想法 & 算法
1.将k 个链表配对并将同一对中的链表合并。
2.第一轮合并以后，k 个链表被合并成了 k/2个链表，平均长度为 2N}/k，然后是 k/4个链表， k/8个链表等等。
3.重复这一过程，直到我们得到了最终的有序链表。

python:

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2
        return lists[0] if amount > 0 else lists

    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1
                l1 = point.next.next
            point = point.next
        if not l1:
            point.next=l2
        else:
            point.next=l1
        return head.next

法二：两两合并链表
整体时间复杂度为O(N*log(k)), k为链表个数，N为链表数组中节点总个数。
整体思路为
1.合并数组中第k个链表到第1个链表，合并数组中第k-1个链表到第2个链表，依次这样操作.
2.一轮合并之后，新链表分布在数组的 第1 到 第(k+1)/2个链表中，继续1这样的合并直到新链表只在数组第一个位置。
3.返回数组第一个元素，即合并之后的链表。

Java:

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }    
        // 将n个链表以中间为对称，合并，即合并 
        while(len>1) {
            for (int i=0; i<len/2; i++) {
                lists[i] = mergeTwoLists(lists[i], lists[len-1-i]);
            }
            len = (len+1)/2;
        }
        return lists[0];
    }
    // 合并两个链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        } else if (l2 != null) {
            p.next = l2;
        }
        return head.next;
}

法三 贪心算法、优先队列
思路分析：

1、由于是 kk 个排序链表，那么这 kk 个排序的链表头结点中 val 最小的结点就是合并以后的链表中最小的结点；

2、最小结点所在的链表的头结点就要更新了，更新成最小结点的下一个结点（如果有的话），此时还是这 kk 个链表，这 kk 个排序的链表头结点中 val 最小的结点就是合并以后的链表中第 22 小的结点。

写到这里，我想你应该差不多明白了，我们每一次都从这 kk 个排序的链表头结点中拿出 val 最小的结点“穿针引线”成新的链表，这个链表就是题目要求的“合并后的排序链表”。“局部最优，全局就最优”，这不就是贪心算法的思想吗。

这里我们举生活中的例子来理解这个思路。
假设你是一名体育老师，有 33 个班的学生，他们已经按照身高从矮到高排好成了 33 列纵队，现在要把这 33 个班的学生也按照身高从矮到高排列 11 列纵队。我们可以这么做：

1、让 33 个班的学生按列站在你的面前，这时你能看到站在队首的学生的全身；
2、每一次队首的 33 名同学，请最矮的同学出列到“队伍4”（即我们最终认为排好序的队列），出列的这一列的后面的所有同学都向前走一步（其实走不走都行，只要你能比较出站在你面前的 3 位在队首的同学同学的高矮即可）；
3、重复第 2 步，直到 33 个班的同学全部出列完毕。

具体实现的时候，“每一次队首的 33 名同学，请最矮的同学出列”这件事情可以交给优先队列（最小堆、最小索引堆均可）去完成。在连续的两次出队之间完成“穿针引线”的工作。

python:

from typing import List
import heapq

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        l = []
        size = len(lists)

        for index in range(size):
            # 针对一些特殊的测试用例，有的链表可能是空链表
            if lists[index]:
                heapq.heappush(l, (lists[index].val, index))

        dummy_node = ListNode(-1)
        cur = dummy_node

        while l:
            _, index = heapq.heappop(l)

            # 定位到此时应该出列的那个链表的头结点
            head = lists[index]
            # 开始“穿针引线”
            cur.next = head
            cur = cur.next
            # 同样不要忘记判断到链表末尾结点的时候
            if head.next:
                # 刚刚出列的那个链表的下一个结点成为新的链表头结点加入优先队列
                heapq.heappush(l, (head.next.val, index))
                # 切断刚刚出列的那个链表的头结点引用
                lists[index] = head.next
                head.next = None
        return dummy_node.next

时间复杂度：O(Nlogk)，这里 NN 是这 kk 个链表的结点总数，每一次从一个优先队列中选出一个最小结点的时间复杂度是 O(logk)，故时间复杂度为 O(Nlogk)。
空间复杂度：O(k)，使用优先队列需要 k个空间，“穿针引线”需要常数个空间，因此空间复杂度为 O(k)。