本文详细介绍了如何在java中使用最小堆高效合并k个有序链表。文章阐述了该算法的核心思想、具体实现步骤，并通过代码示例展示了如何构建和操作链表。特别地，本文深入解析了在链表构建过程中，head和last这两个关键指针如何协同工作，确保合并后的链表正确连接，并澄清了head指针如何“感知”到last指针所做的修改。
1. 问题背景与最小堆合并策略
合并K个已排序的链表是一个常见的算法问题，目标是将这些链表中的所有节点按升序排列，形成一个新的单一链表。一个直观但效率不高的方法是两两合并，其时间复杂度会较高。更优的解决方案是利用最小堆（优先队列）的特性。最小堆能够实时维护所有链表当前头节点中的最小值，从而确保我们每次都能取出全局最小的元素，并将其添加到结果链表中。
该策略的核心思想是：
- 将K个链表的第一个节点（头节点）全部放入一个最小堆中。
- 每次从堆中取出最小的节点。
- 将取出的节点添加到结果链表中。
- 如果取出的节点还有下一个节点，则将其下一个节点也放入堆中。
- 重复步骤2-4，直到堆为空。
2. Java实现：核心数据结构与算法流程
在Java中实现这一算法，我们需要定义链表节点、自定义比较器以及主合并函数。
2.1 链表节点定义
一个标准的单向链表节点包含数据和指向下一个节点的引用。
立即学习“Java免费学习笔记（深入）”；
class Node {
int data;
Node next;
Node(int key) {
data = key;
next = null;
}
}2.2 自定义比较器
PriorityQueue在Java中默认实现的是最小堆，但它需要知道如何比较自定义对象（如Node对象）。因此，我们需要实现Comparator接口来定义节点的比较规则，即根据data字段进行升序比较。
import java.util.Comparator; import java.util.PriorityQueue; // 导入PriorityQueue class NodeComparator implements Comparator{ @Override public int compare(Node k1, Node k2) { if (k1.data > k2.data) return 1; // k1 大于 k2 else if (k1.data < k2.data) return -1; // k1 小于 k2 return 0; // k1 等于 k2 } }
2.3 mergeKList 函数实现
这是算法的核心部分，负责协调最小堆和链表构建。
class GFG {
static Node mergeKList(Node[] arr, int K) {
// 使用自定义比较器初始化最小优先队列
PriorityQueue queue = new PriorityQueue<>(new NodeComparator());
// 创建一个虚拟头节点（dummy head），用于简化链表操作
Node head = new Node(0);
// last指针将始终指向当前结果链表的尾部
Node last = head;
// 将所有K个链表的头节点（如果非空）添加到优先队列中
for (int i = 0; i < K; i++) {
if (arr[i] != null) {
queue.add(arr[i]);
}
}
// 处理K=0或所有链表为空的情况
if (queue.isEmpty())
return null;
// 当优先队列不为空时，循环执行
while (!queue.isEmpty()) {
// 取出堆顶元素（当前所有链表头节点中的最小值）
Node curr = queue.poll();
// 将curr节点添加到结果链表的尾部
last.next = curr;
// 更新last指针，使其指向新添加的节点
last = last.next;
// 如果curr节点所属的链表还有后续节点，则将其下一个节点加入优先队列
if (curr.next != null) {
queue.add(curr.next);
}
}
// 返回合并后链表的实际头节点（跳过虚拟头节点）
return head.next;
}
// 辅助函数：打印链表
public static void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// 主函数示例
public static void main(String[] args) {
int N = 3;
Node[] a = new Node[N];
// 链表1: 1->3->5->7
Node head1 = new Node(1);
a[0] = head1;
head1.next = new Node(3);
head1.next.next = new Node(5);
head1.next.next.next = new Node(7);
// 链表2: 2->4->6->8
Node head2 = new Node(2);
a[1] = head2;
head2.next = new Node(4);
head2.next.next = new Node(6);
head2.next.next.next = new Node(8);
// 链表3: 0->9->10->11
Node head3 = new Node(0);
a[2] = head3;
head3.next = new Node(9);
head3.next.next = new Node(10);
head3.next.next.next = new Node(11);
Node res = mergeKList(a, N);
if (res != null)
printList(res);
System.out.println(); // 输出结果：0 1 2 3 4 5 6 7 8 9 10 11
}
} 3. 关键指针机制解析：head与last的协同工作
在mergeKList函数中，head和last这两个指针的初始化和更新方式是理解链表构建过程的关键。
Node head = new Node(0); // 虚拟头节点 Node last = head; // last指针初始指向虚拟头节点
-
初始化状态：head和last都指向同一个新创建的虚拟节点（data: 0, next: null）。这个虚拟节点本身不包含任何有效数据，它的作用是作为合并后链表的起点，避免在处理第一个实际节点时进行特殊判断。
head last ↓ ↓ ┌────────────┐ │ data: 0 │ │ next: null │ └────────────┘
-
添加第一个实际节点： 假设从优先队列中取出的第一个节点是curr（例如，data: 0，来自链表3）。 执行 last.next = curr; 时：
- last当前指向虚拟节点。
- last.next修改的是虚拟节点的next字段，使其指向curr节点。
- 由于head也指向这个虚拟节点，所以head.next也随之指向了curr节点。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 0 │ │ next: ─────────►│ next: 9 │ └────────────┘ └────────────┘
-
更新last指针： 紧接着执行 last = last.next; 时：
- last指针从虚拟节点移动到刚刚添加的curr节点（即data: 0的节点）。
- 此时，head仍然指向最初的虚拟节点，而last则指向合并链表的当前尾部。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 0 │ │ next: ─────────►│ next: 9 │ └────────────┘ └────────────┘
后续节点添加： 当循环继续，从优先队列中取出下一个最小节点（例如，`data
