leetcode23

``
merge sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if len(lists)==0:
            return None
        
        n = len(lists)
        while n>1:
            k = (n+1)/2   # 加1是希望每次前一半和后一半配对
            for i in range(n/2):
                lists[i] = self.mergeTwoLists(lists[i], lists[i+k])
            # 弄完之后要更新n
            n = k

        return lists[0]
        
    def mergeTwoLists(self, lst1, lst2):
        ret = ListNode(-1)
        temp = ret
        
        # 让temp往前进
        
        while lst1 and lst2:
            if lst1.val<lst2.val:
                temp.next = lst1
                lst1 = lst1.next
                
            else:
                temp.next = lst2
                lst2 = lst2.next
            
            temp = temp.next
        
        # 别忘了最后的
        if lst1:
            temp.next = lst1
        else:
            temp.next = lst2
            
        return ret.next