【leetcode】23.合并K个排序链表

合并 k 个排序链表&＃xff0c;返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

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

分析&＃xff1a;

我想是k次归并。时间复杂度是(k-1)nlogn。

参考的思路是&＃xff1a;

题目分析&＃xff1a;本题首先将每个链表的首元素取出&＃xff0c;构建一个最小堆。堆顶则为最小的元素&＃xff0c;用最小元素所在的那个链表的第二个元素替换掉它的位置。然后维护最小堆的特性&＃xff0c;再取出堆顶元素&＃xff0c;……&＃xff0c;一直到所有链表元素都取出为止。

时间复杂度分析&＃xff1a;一共是K个链表&＃xff0c;假设每个链表有n个元素&＃xff0c;首先是K个链表首元素的建堆&＃xff0c;花费O(K)&＃xff0c;然后取堆顶元素&＃xff0c;用下一个元素替换掉它&＃xff0c;维护最小堆的特性&＃xff0c;花费O(lgK)&＃xff0c;共有K*n个元素&＃xff0c;所以花费(K*n-1)*lgK的时间&＃xff0c;故总时间为O(K*n*lgK)

我们用优先队列来实现&＃xff0c;优先队列的底层是用堆实现的。所谓优先&＃xff0c;指的是队列里的元素按照优先级大小排列&＃xff0c;优先级大的排在前面&＃xff0c;优先级相同的按照入队的顺序排列。首先将每个链表的首元素入队&＃xff0c;将最小元素置于堆顶&＃xff0c;然后找最小元素所在链表的下一个元素入队&＃xff0c;一直到队为空。

from queue import PriorityQueue
# from heapq import heappush,heappop
class Solution(object):def mergeKLists(self, lists):dummy &＃61; curr &＃61; ListNode(None)q &＃61; PriorityQueue()for idx,node in enumerate(lists):# 我的妈&＃xff0c;链表竟然可以这样遍历# print(idx,node) # TypeError: &＃39;ListNode&＃39; object is not iterable# 不可以这样遍历- -if node:q.put((node.val,idx,node))# print(q.get()) # (1, 0, <__main__.ListNode object at 0x105d20518>)while not q.empty():# 最小的元素在链表尾部_,idx,curr.next &＃61; q.get()curr &＃61; curr.nextif curr.next:q.put((curr.next.val,idx,curr.next))return dummy.next


## using minheap
def mergeKLists2(self, lists):dummy &＃61; curr &＃61; ListNode(None)heap &＃61; []for idx, node in enumerate(lists):if node:heappush(heap, (node.val, idx, node))while heap:_, idx, curr.next &＃61; heappop(heap)curr &＃61; curr.nextif curr.next:heappush(heap, (curr.next.val, idx, curr.next))return dummy.next

详细用法&＃xff1a;Python堆和优先队列的使用

参考&＃xff1a; 

原文&＃xff1a;https://blog.csdn.net/Jaster_wisdom/article/details/81332854

https://leetcode.com/problems/merge-k-sorted-lists/discuss/261487/Simple-Python-solution-using-PriorityQueue-and-MinHeap