Leetcode 23. Merge k Sorted List

Question:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Thinking

一个很自然的想法就是两两合并。现在假设有l1,l2,l3...ln那么现将l1,l2合并，合并后的新list（不妨叫做l12）再和l3合并，然后一直做下去，但是考虑一下这样的时间复杂度。假设对应的长度分别是m1,m2,...mn，这样需要遍历的次数是：
m1 + m2 (l1,l2合并)
m1 + m2 + m3 (l1+l2 和 l3 合并)
m1 + m2 + m3 + m4
.....
m1 + m2 + m3 ..... + mn *
综合的时间复杂度是把上面的全都加起来
那就是：
n * m1 + n * m2 + (n-1) * m3 + (n-2)m4 + .... mn
这个时间复杂度还是很巨大的。这样做不合理的原因就是很多项被重复合并了很多次。
改进的想法是这样的： m1 和 m2 合并， m3 和 m4合并 .... m(n-1) 和 mn合并,然后再两两合并，最终只剩下一个为止，这样每一个链表都只被合并了一次，时间复杂度是0(N).当然，具体实现的时候仍然可以考虑用递归来实现。

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        p1 = list1
        p2 = list2
        head = ListNode('#')
        p = head
        while p1 is not None and p2 is not None:
            if p1.val <= p2.val:
                p.next = p1
                p1 = p1.next
            else:
                p.next = p2
                p2 = p2.next
            p = p.next
        while p1 is not None:
            p.next = p1
            p1 = p1.next
            p = p.next
        while p2 is not None:
            p.next = p2
            p2 = p2.next
            p = p.next
        # since the first element is what we defined '#'
        # and that is totally for mark
        return head.next



    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        size = len(lists)
        if size == 2:
            head = self.mergeTwoLists(lists[0], lists[1])
        elif size == 1:
            head = lists[0]
        elif size == 0:
            head = None
        else:
            mid = size / 2
            list1 = self.mergeKLists(lists[0:mid])
            list2 = self.mergeKLists(lists[mid:size])
            head = self.mergeTwoLists(list1, list2)
        return head

Performance