脚本宝典收集整理的这篇文章主要介绍了Merge k Sorted Lists,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
1.解题思路
这题是Merge Two Sorted Lists的拓展,我们当然也可以利用两两归并来实现,但这里我们采用PriorityQueue实现更简洁清晰。
最小堆,队列顶端的元素永远是最小的,那我们把k个列表的第一个元素放入队列后,取出队列顶端的节点,就是需要找的最小的节点。
注意点:
1)PriorityQueue不接受null值,add前需要判断;
2)取出队列顶端节点后,要将该节点的next节点放进队列中。
3)需要实现一个Comparator<ListNode>
2.代码
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
//min heap
PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(11,new Comparator<ListNode>(){
public int compare(ListNode l1,ListNode l2){
return l1.val-l2.val;
}
} );
ListNode dummy=new ListNode(0);
for(int i=0;i<lists.length;i++){
if(lists[i]!=null)
pq.add(lists[i]);
}
ListNode node=dummy;
while(pq.peek()!=null){
node.next=pq.poll();
node=node.next;
if(node.next!=null)
pq.add(node.next);
}
return dummy.next;
}
}
以上是脚本宝典为你收集整理的Merge k Sorted Lists全部内容,希望文章能够帮你解决Merge k Sorted Lists所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。