1.题目

原题

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

例子

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

2.解析

这道题实在排序两个有序链表上的升级。
其实思路很简单，只需要依次合并列表中的两个链表，然后合并后的链表跟下一个链表合并，直到合并完成即可，但是这种方法效率比较低，提交以后只打败了5%的提交者。
于是笔者采用了分治策略，降低算法的复杂度，但效率提升不高，大约击败20%的提交者。分治策略，用到了递归，各位看官要理解递归的输出。

3.python代码

class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists) // 2
        left = len(lists) % 2
        llists = lists[0: mid]
        rlists = lists[mid:]
        l = self.mergeKLists(llists)
        r = self.mergeKLists(rlists)
        f = self.mergeTwoLists(l, r)
        return f

    def mergeTwoLists(self, list1, list2):
        head = ListNode(0)
        newl = head
        while list1 is not None or list2 is not None:#根据链表的特点
            if list1 is None:
                head.next = list2
                break
            if list2 is None:
                head.next = list1
                break
            if list1.val < list2.val:
                head.next = list1
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next
        return newl.next