合并K个有序链表是指将多个已经按升序排列的链表合并成一个新的升序链表，传统的逐个链表合并方式时间复杂度较高，而使用最小堆可以将时间复杂度优化到更合理的范围。在合并过程中，头尾指针的维护是保证结果链表正确拼接的关键，下面我们逐步展开讲解。
一、最小堆合并K个有序链表的基础思路
最小堆是一种特殊的完全二叉树，每个父节点的值都小于等于其子节点的值，堆顶元素永远是堆中最小的元素。合并K个有序链表时，我们可以先把每个非空链表的头节点放入最小堆中，每次取出堆顶的最小节点，将这个节点接到结果链表的末尾，再把该节点的下一个节点（如果存在）放入最小堆，重复这个过程直到堆为空，就能得到合并后的有序链表。
Java中可以使用PriorityQueue类来实现最小堆，默认情况下PriorityQueue是最小堆结构，我们只需要自定义比较规则，让堆按照链表节点的值进行排序即可。
二、链表节点定义与最小堆初始化
首先我们需要定义链表节点的结构，常规的链表节点包含两个属性：节点值和指向下一个节点的指针。
// 定义链表节点类
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
接下来初始化最小堆，我们需要指定优先队列的比较器，让它按照节点值升序排列，这样堆顶就是当前所有节点中值最小的节点。
import java.util.PriorityQueue;
import java.util.Comparator;
public class MergeKLists {
public ListNode mergeKLists(ListNode[] lists) {
// 初始化最小堆，自定义比较规则：按节点值升序排列
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode a, ListNode b) {
return a.val - b.val;
}
});
// 将所有非空链表的头节点加入堆中
for (ListNode node : lists) {
if (node != null) {
minHeap.offer(node);
}
}
// 后续合并逻辑会在这里补充
return null;
}
}
三、头尾指针机制的作用与实现
在合并过程中，我们需要构建结果链表，头指针用来记录结果链表的第一个节点，方便最后返回整个链表；尾指针用来记录当前结果链表的最后一个节点，每次取出最小节点后，直接把新节点接到尾指针的后面，不需要每次都从头遍历结果链表，能提升拼接效率。
初始时结果链表为空，头指针和尾指针都为null，当第一次从堆中取出节点时，我们同时把头指针和尾指针指向这个节点；后续每次取出节点时，只需要把尾指针的next指向新节点，再更新尾指针为新节点即可。
头尾指针的具体维护步骤
- 初始化头指针
head和尾指针tail都为null - 从最小堆取出当前最小节点
curNode - 如果
head为null，说明是第一个节点，将head和tail都赋值为curNode - 如果
head不为null，将tail.next指向curNode，再更新tail为curNode - 如果
curNode有下一个节点，将下一个节点加入最小堆 - 重复上述步骤直到最小堆为空
四、完整代码实现
下面是结合最小堆和头尾指针机制的完整合并实现：
import java.util.PriorityQueue;
import java.util.Comparator;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class MergeKLists {
public ListNode mergeKLists(ListNode[] lists) {
// 1. 初始化最小堆，按节点值升序排列
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode a, ListNode b) {
return a.val - b.val;
}
});
// 2. 将所有非空链表的头节点加入堆
for (ListNode node : lists) {
if (node != null) {
minHeap.offer(node);
}
}
// 3. 初始化头尾指针
ListNode head = null;
ListNode tail = null;
// 4. 循环处理堆中的节点
while (!minHeap.isEmpty()) {
// 取出当前最小的节点
ListNode curNode = minHeap.poll();
// 维护头指针：如果是第一个节点，头尾都指向它
if (head == null) {
head = curNode;
tail = curNode;
} else {
// 维护尾指针：把新节点接到尾节点后面，更新尾节点
tail.next = curNode;
tail = curNode;
}
// 如果当前节点有下一个节点，加入堆中
if (curNode.next != null) {
minHeap.offer(curNode.next);
}
}
// 返回合并后的链表头节点
return head;
}
}
五、复杂度分析
假设K是链表的数量，N是所有链表的节点总数：
| 指标 | 说明 |
|---|---|
| 时间复杂度 | 初始化堆需要O(K)时间，每次堆操作是O(logK)，总共有N个节点，所以总时间是O(NlogK) |
| 空间复杂度 | 堆中最多存放K个节点，所以额外空间是O(K) |
头尾指针的使用不会增加额外的空间复杂度，只是两个额外的引用变量，相比每次拼接都遍历结果链表的方式，能减少很多不必要的时间消耗。
六、注意事项
- 加入堆之前一定要判断链表头节点是否为null，避免空指针异常
- 比较器的逻辑要正确，保证是最小堆而不是最大堆，否则合并出来的链表是降序的
- 尾指针更新之后，不需要手动把新节点的next设为null，因为原来链表节点的next已经指向下一个节点，或者本身就是最后一个节点
- 如果输入的链表数组为空或者所有链表都为空，函数会正确返回null，不需要额外处理