leetcode 合并K个升序链表

leetcode 合并K个升序链表

 这是道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个升序链表

上一篇:retrofit原理,JVM虚拟机原理深入解析,互联网行业“中年”危机


下一篇:[整理] POP3、SMTP、IMAP、CardDAV、CalDAV 之间的区别和联系