leetcode--合并K個排序鏈表

發(fā)布時間：2020-03-31 16:21:15 來源：網(wǎng)絡(luò) 閱讀：385 作者：ading2016 欄目：編程語言

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

示例:

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

#?Definition?for?singly-linked?list.
#?class?ListNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.next?=?None
import?heapq
class?Solution:
????def?mergeKLists(self,?lists:?List[ListNode])?->?ListNode:
????????h?=?[]
????????for?node?in?lists:
????????????while?node:
????????????????h.append(node.val)
????????????????node?=?node.next
????????if?not?h:
????????????return?None
????????heapq.heapify(h)?#轉(zhuǎn)換成最小堆
????????#?構(gòu)造鏈表
????????root?=?ListNode(heapq.heappop(h))
????????curnode?=?root
????????while?h:
????????????nextnode?=?ListNode(heapq.heappop(h))
????????????curnode.next?=?nextnode
????????????curnode?=?nextnode
????????return?root

執(zhí)行用時 :?104 ms, 在Merge k Sorted Lists的Python3提交中擊敗了77.24% 的用戶

內(nèi)存消耗 :?17.2 MB, 在Merge k Sorted Lists的Python3提交中擊敗了42.33% 的用戶

向AI問一下細節(jié)

leetcode--合并K個排序鏈表

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標簽