这是我参与更文挑战的第20天，活动详情查看：更文挑战

前言

力扣第二十三题 合并K个升序链表 如下所示：

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

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组为：[1->4->5,1->3->4, 2->6]，将它们合并到一个有序链表中得到：1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

一、思路

这一题和之前的力扣 第二十一题-合并两个有序链表 基本是一致的，不过思路要稍作改变。

大体的步骤分为以下几个步骤：

拿到所有链表的第一个节点
比较各链表中的当前值，选取最小的值加入新链表，并将已加入链表的节点指向 next
重复步骤2

上面的实现步骤其实正好可以使用Java中的优先队列来实现，在实现过程中只需要关注何时向优先队列中加入元素和取元素即可。

优先队列中存储的是是一个基于优先处理的对象，即实现 Comparable 接口的类。
特别要注意的是，其实优先队列中实现 Comparable 接口是为了在插入元素时，将元素放到对应的位置，以保证第一个出来的是权值最小的（即 compareTo 返回的最小值）

图解优先队列

此处以示例1中的 [[1,4,5],[1,3,4],[2,6]] 作为例子
红色字：表示在优先队列中存储的值（以三个链表为例，队列中至多只会存储三个优先处理对象）
红色字后面的绿色字：表示它在优先队列中的存储位置
ret：结果集

初始情况，如下图所示

取出最小值1，并加入选择节点的后面一个节点4加入到优先队列。如下图所示：

继续取出最小值1，并加入选择节点的后面一个节点3加入到优先队列。如下图所示：

以此类推，结果集中会依次加入 2, 3 ，如下图所示：

后面再将 4, 4, 5, 6 加入到结果集即可得到最终结果 1->1->2->3->4->4->5->6

二、实现

代码实现

    class Status implements Comparable<Status> {
        int val;
        ListNode node;

        public Status(int val, ListNode node) {
            this.val = val;
            this.node = node;
        }

        // 自定义对象的比较方式
        @Override
        public int compareTo(Status o) {
            return this.val - o.val;
        }
    }

    /**
     * 优先队列
     * tips：官方推荐思路
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ret = new ListNode();
        ListNode temp = ret;
        // 优先队列
        PriorityQueue<Status> queue = new PriorityQueue<>();
        // 将非空的链表加入到优先队列
        for (ListNode node : lists) {
            if (node != null)
                // 添加到队列中
                queue.offer(new Status(node.val, node));
        }
        while (!queue.isEmpty()) {
            // 找到并移除优先队列中最小的值
            Status f = queue.poll();
            temp.next = new ListNode(f.val);
            temp = temp.next;
            // 如该链表仍有元素，则继续入队
            if (f.node.next != null) {
                queue.offer(new Status(f.node.next.val, f.node.next));
            }
        }
        return ret.next;
    }
复制代码

测试代码

    public static void main(String[] args) {
        // [[1,4,5],[1,3,4],[2,6]]
        ListNode[] arr = new ListNode[3];
        arr[0] = new ListNode(1, new ListNode(4, new ListNode(5)));
        arr[1] = new ListNode(1, new ListNode(3, new ListNode(4)));
        arr[2] = new ListNode(2, new ListNode(6));
        new Number23().mergeKLists(arr);
    }
复制代码