1.题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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 =
输出：[]

提示：
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] 按 升序 排列
lists[i].length 的总和不超过 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

2.思路

（1）双指针和优先级队列
由题可知，一共有 k 个链表。而一般来说，在合并的过程中肯定涉及到在 k 个结点中寻找值最小的结点，这里就涉及到了排序问题，所以我们可以考虑使用 Java 中的优先级队列 PriorityQueue。具体的解题思路如下：
① 定义虚拟头结点 dummy 、指向 dummy 的结点 p（用于指向结果链表）、优先级队列 queue（优先级规则是结点值小的在前）；
② 将 k 个链表的头结点加入队列中；
③ 用 poll() 发方法获取当前队列中值最小的结点 node ，然后将 node 连接到 p 之后。如果 node.next != null ，说明结点 node 所在的链表还未遍历结束，故将 node 的下一个结点加入到队列中，之后，p 向前移动。
④ 当队列 queue 为空时，说明所有的链表已经遍历结束，返回结果链表的头结点 dummy.next 即可。

3.代码实现（Java）

//思路1————双指针
/**
 * 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 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int k = lists.length;
        //定义虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        //定义优先级队列
        PriorityQueue<ListNode> queue = new PriorityQueue<>(
                //队列长度为链表的个数
                k,
                //定义优先级规则
                (a, b) -> (a.val - b.val)
        );
        //将 k 个链表的头结点加入队列中
        for (ListNode head : lists) {
            if (head != null) {
                queue.add(head);
            }
        }
        while (!queue.isEmpty()) {
            //获取当前队列中值最小的结点
            ListNode node = queue.poll();
            p.next = node;
            if (node.next != null) {
                //将node的下一个结点加入到队列中
                queue.add(node.next);
            }
            //p指针向前移动
            p = p.next;
        }
        return dummy.next;
    }
}