leetcode23-- Merget k sorted lists (归并)

leetcode23-- Merget k sorted lists (归并)

题目

``
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

之前做了一个merge两个的,那这个其实本质上和那个是一样的,只不过需要用一下归并,即上前半段的去和后半段的归并一下,最终返回第一个就可以了。


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

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦