• 題目描述：把k個排序的鏈表組成的列表合并成一個排序的鏈表

• 思路：

使用堆排序，遍歷列表，把每個列表中鏈表的頭指針的值和頭指針本身作為一個元素放在堆中；

第一步中遍歷完列表后，此時堆中最多會有n個元素，n是列表的長度；

當(dāng)堆不為空，取出堆中的最小值，然后把該值的指針指向下一個元素，并入堆；

第3步可以確保堆永遠是o(n)大小的；

堆為空返回頭結(jié)點就可以了

# 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"""import heapqmin_heap = []ret = head = ListNode(0)for k, link in enumerate(lists):if link:heapq.heappush(min_heap, [link.val, link])while min_heap:cur = heapq.heappop(min_heap)ret.next = cur[-1]ret = ret.nextif ret.next:heapq.heappush(min_heap, [ret.next.val, ret.next])return head.next

轉(zhuǎn)載于:https://www.cnblogs.com/qiaojushuang/p/8082906.html

總結(jié)

以上是生活随笔為你收集整理的Python 解LeetCode：23. Merge k Sorted Lists的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。