一、问题描述：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
二、解题思路：
- 当合并K个有序链表时，我们可以利用优先队列来简化这个过程。每次从优先队列中取出一个值最小的节点加入链表中，再从该节点所属的链表中取出下一个节点加入优先队列，直到所有的节点都遍历一次。
- 具体步骤：
①**创建结果链表和当前节点指针：代码开始时，创建了一个虚拟头节点 result 和一个当前节点指针 cur，它们都指向虚拟头节点。
②使用优先队列存储节点：创建了一个优先队列 pq，它根据节点的值来比较大小，小的节点排在队列前面。
③将每个链表的头节点加入优先队列：遍历输入的链表数组 lists，将每个链表的头节点加入优先队列 pq 中。
④合并链表：使用优先队列进行合并操作，每次取出队列中值最小的节点，将其加入结果链表，并将其下一个节点加入优先队列中，直到优先队列为空。
⑤返回结果链表：**返回结果链表的头节点。
三、代码示例：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 判断输入的链表数组是否为空
if (lists.length == 0) return null;
// 创建一个虚拟头节点作为结果链表的起始节点
ListNode result = new ListNode(-1);
// 创建一个当前节点指针，用于构建结果链表
ListNode cur = result;
// 创建一个优先队列，用于存储链表节点，并按节点值进行排序
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
// 按节点值升序排序
return o1.val - o2.val;
}
});
// 将所有链表的头节点加入优先队列
for (ListNode list : lists) {
if (list != null) {
pq.offer(list);
}
}
// 使用优先队列进行链表合并
while (!pq.isEmpty()) {
// 取出优先队列中值最小的节点
ListNode s = pq.poll();
// 将取出的节点加入结果链表
cur.next = s;
// 更新当前节点指针
cur = cur.next;
// 如果取出的节点还有下一个节点，则将下一个节点加入优先队列
if (s.next != null) {
pq.offer(s.next);
}
}
// 返回结果链表的头节点
return result.next;
}
}
- 时间复杂度分析：
假设 K 是输入链表数组的长度，N 是所有链表节点的总数。
**建立优先队列：**将所有链表的头节点加入优先队列，时间复杂度为 O(K * logK)，因为优先队列的大小最多为 K。
**合并操作：**每次从优先队列中取出一个节点并插入一个节点，优先队列的大小最多为 K，而每个节点最多只会被插入和取出一次。所以，合并操作的时间复杂度为 O(N * logK)。
