23-Merge-k-Sorted-Lists

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

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

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)O(Nlogk)$$，其中 text{k}k 是链表的数目。

我们可以在 O(n)O(n) 的时间内合并两个有序链表，其中 nn 是两个链表中的总节点数。
将所有的合并进程加起来，我们可以得到：$$O\big(\sum_{i=1}^{log_2k}N\big)= O(N\logk)O(∑i=1log2kN)=O(Nlogk)$$
空间复杂度：O(1)

我们可以用 O(1)的空间实现两个有序链表的合并。