leetcode23. 合并K个排序链表

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

示例:

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

# python
# 分治法（递归）
class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if lists==None or len(lists)==0: return None
        if len(lists) == 1: return lists[0]
        return self.doMerge(lists, 0, len(lists)- 1)

    def doMerge(self,lists,left,right):
        if left==right:return lists[left]
        elif left+1==right: return self.mergeTwoLists(lists[left],lists[right])
        l1 = self.doMerge(lists, left, (left + right) // 2)
        l2 = self.doMerge(lists, (left+right)//2+1, right)
        return self.mergeTwoLists(l1, l2)

    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = idx = ListNode(None)
        while l1!=None or l2!=None:
            if l2==None or (l1!=None and l1.val <= l2.val):
            # if判断中一开始少了 `l1!=None` 是不行的，l1空l2不空的时候不能进行l1.val <= l2.val
                idx.next = l1
                idx = idx.next
                l1 = l1.next
            else:
                idx.next = l2
                idx = idx.next
                l2 = l2.next
        return head.next