首页 > 其他 > 详细

leetcode 合并K个升序链表

时间:2021-09-01 15:46:42      阅读:18      评论:0      收藏:0      [点我收藏+]

技术分享图片

 这是道hard题,在处理时需要用到优先队列(PriorityQueue),即我们将每个链表的头结点放入最小堆中,每次取出最小的结点插入最终返回的链表。

当优先队列中不存在结点时,我们就得到了需要的链表。

    public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length==0)
                return null;
            ListNode dummy=new ListNode();
            ListNode p=dummy;
            PriorityQueue<ListNode> pq=new PriorityQueue<>(lists.length,(a,b) ->(a.val-b.val));
            for(ListNode head :lists)
            {
                if(head!=null)
                pq.add(head);
            }

            while(!pq.isEmpty())
            {
                ListNode node=pq.poll();
                p.next=node;
                if(node.next!=null)
                {
                    pq.add(node.next);
                }
                p=p.next;
            }
            return dummy.next;
    }

 

leetcode 合并K个升序链表

原文:https://www.cnblogs.com/xxsdbk/p/15208822.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!