Question:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Thinking
一個很自然的想法就是兩兩合并。現(xiàn)在假設(shè)有l1,l2,l3...ln那么現(xiàn)將l1,l2合并硼啤，合并后的新list（不妨叫做l12）再和l3合并粟矿，然后一直做下去励烦，但是考慮一下這樣的時間復(fù)雜度簸喂。假設(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 *
綜合的時間復(fù)雜度是把上面的全都加起來
那就是：
n * m1 + n * m2 + (n-1) * m3 + (n-2)m4 + .... mn
這個時間復(fù)雜度還是很巨大的刽锤。這樣做不合理的原因就是很多項被重復(fù)合并了很多次彪蓬。
改進(jìn)的想法是這樣的： m1 和 m2 合并， m3 和 m4合并 .... m(n-1) 和 mn合并,然后再兩兩合并悲立，最終只剩下一個為止鹿寨，這樣每一個鏈表都只被合并了一次，時間復(fù)雜度是0(N).當(dāng)然薪夕，具體實現(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
每次都不一樣
