Question:

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

Thinking

一個很自然的想法就是兩兩合并?，F(xiàn)在假設(shè)有l1,l2,l3...ln那么現(xiàn)將l1,l2合并，合并后的新list（不妨叫做l12）再和l3合并，然后一直做下去，但是考慮一下這樣的時間復雜度。假設(shè)對應(yīng)的長度分別是m1,m2,...mn，這樣需要遍歷的次數(shù)是：
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).當然，具體實現(xiàn)的時候仍然可以考慮用遞歸來實現(xià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

每次都不一樣