c++如何合并K個(gè)排序鏈表

這篇“c++如何合并K個(gè)排序鏈表”文章的知識點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“c++如何合并K個(gè)排序鏈表”文章吧。

合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復(fù)雜度。

示例:

輸入:[
  1->4->5,
  1->3->4,
  2->6
]輸出: 1->1->2->3->4->4->5->6

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        #合成一個(gè)大的listlist然后排序
        lists = [x for x in lists if x]        if not lists or all([not x for x in lists]): return 
        head = lists.pop()
        
        curr = head        while curr.next:
            curr = curr.next            
        while lists:
            tmp = lists.pop()
            curr.next = tmp            while tmp.next:
                tmp = tmp.next
            curr = tmp        
        if not head or not head.next: return head        return self.mergeSort(head)    
    def mergeSort(self, head):
        if not head.next: return head
        pre, slow, fast = None, head, head        
        while fast and fast.next:
            prev, slow, fast = slow, slow.next, fast.next.next
        
        prev.next = None
        left = self.mergeSort(head)
        right = self.mergeSort(slow)        return self.merge(left, right)    
    def merge(self, left, right):
        if not left:            return right        if not right:            return left        
        if left.val < right.val:
            res = left
            res.next = self.merge(left.next, right)        else:
            res = right
            res.next = self.merge(left, right.next)        return res

以上就是關(guān)于“c++如何合并K個(gè)排序鏈表”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。