LeetCode刷题笔记 Java 腾讯 链表 合并K个排序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

LeetCode刷题笔记 Java 腾讯 链表 合并K个排序链表

类似于合并两个排序列表,但是此处需要用一个优先队列储存所有队列。

取出最小值放入结果列表尾部,并把其下一个位置放入队列。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0||lists==null){
            return null;
        }
        ListNode pre=new ListNode();
        ListNode head=pre;
        PriorityQueue<ListNode> p=new PriorityQueue(new Comparator<ListNode>(){
            public int compare(ListNode t1,ListNode t2){
                return t1.val-t2.val;
            }
        });
        for(ListNode list:lists){
            if(list!=null){
                p.offer(list);
            }
        }
        while(!p.isEmpty()){
            head.next=p.poll();
            head=head.next;
            // 此处head.next相当于q.poll的后一个 如果为空则说明该链表已经空了
            if(head.next!=null){
                p.offer(head.next);
            }
        }
        return pre.next;
    }
}

上一篇:剑指 Offer 24. 反转链表


下一篇:golang力扣leetcode 24.两两交换链表中的节点