[数据结构与算法]23. 合并K个升序链表 (小根堆)

用小根堆(优先队列实现)的方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 实现比较接口
    // class MyComparator implements Comparator<ListNode>{
    //     @Override
    //     public int compare(ListNode n1,ListNode n2){
    //         // 升序排序
    //         return n1.val - n2.val;
    //     }
    // }
    public ListNode mergeKLists(ListNode[] lists) {
        // 创建最小堆(用优先队列实现)
        Queue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>(){
            public int compare(ListNode n1,ListNode n2){
                return n1.val - n2.val;
            }
        });
        // 遍历链表数组的所有子链表
        for(ListNode head : lists){
            // 各个子链表的所有节点全加入到队列,形成最小堆(从小到大排序)
            while(head != null){
                q.offer(head);
                head = head.next;
            }
        }
        // 创建一个副本链表
        ListNode dummy = new ListNode(0);
        // 定义头指针
        ListNode head = dummy;
        // 当队列容量不为空,队列中最小元素依次加入到副本链表
        while(q.size() > 0){
            // 移除并获取队列最小元素
            ListNode temp = q.poll();
            // 赋值给副本节点
            head.next = temp;
            // 副本节点头指针后移
            head = head.next;
            // 当队列容量为0,结束副本节点赋值,防止出现多个重复的值,循环赋值
            if(q.size() == 0) head.next = null;
        }
        // 返回副本链表的第一个节点
        return dummy.next;
    }
}

书森