Code More Create

Appearance

Return to top
On this page

23.合并K个升序链表

题目描述

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

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

思路分析

优先队列的应用

AC 代码 

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        ListNode res = new ListNode(-1);
        ListNode tmp = res;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->a.val - b.val);
        // 把头结点都加进去
        for(ListNode list:lists){
            if(list != null){
                pq.add(list);
            }
        }
        while(!pq.isEmpty()){
            // 取出一个，链接到链表中
            ListNode node = pq.poll();
            tmp.next = node;
            // 如果还有后续结点，加到队列中
            if(node.next != null){
                pq.add(node.next);
            }
            tmp = tmp.next;
        }
        return res.next;
    }
}