Python 解LeetCode：23. Merge k Sorted Lists

• 题目描述：把k个排序的链表组成的列表合并成一个排序的链表

• 思路：

使用堆排序，遍历列表，把每个列表中链表的头指针的值和头指针本身作为一个元素放在堆中；

第一步中遍历完列表后，此时堆中最多会有n个元素，n是列表的长度；

当堆不为空，取出堆中的最小值，然后把该值的指针指向下一个元素，并入堆；

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

堆为空返回头结点就可以了

# 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

转载于:https://www.cnblogs.com/qiaojushuang/p/8082906.html

总结

以上是生活随笔为你收集整理的Python 解LeetCode：23. Merge k Sorted Lists的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。