本文详细介绍了如何利用最小堆高效合并 k 个已排序的链表。通过构建一个虚拟头节点和尾指针，并利用优先级队列动态维护各链表当前最小元素，逐步构建合并后的有序链表。文章将深入解析指针操作的机制，特别是`head`和`last`如何协同工作，确保合并过程的正确性，并提供完整的java代码示例及详细解释。
合并 K 个有序链表问题概述
合并 K 个有序链表是一个经典的算法问题，目标是将 K 个已经排序的链表合并成一个单一的、同样有序的链表。一个直观但效率不高的方法是两两合并，但这种方法的时间复杂度较高。更高效的解决方案是利用最小堆（优先级队列）来管理所有链表的当前最小元素。
最小堆方法的核心思想
最小堆方法的核心思想是：在任意时刻，我们只需要知道 K 个链表中所有当前未处理节点的最小值。优先级队列（Min-Heap）能够高效地提供这一功能。
- 初始化堆： 将 K 个链表的第一个节点（如果存在）全部加入最小堆。堆会根据节点的值进行排序，确保堆顶始终是所有节点中的最小值。
-
构建结果链表：
- 从堆中取出最小元素（堆顶）。
- 将该元素添加到结果链表中。
- 如果该元素所属的链表还有下一个节点，则将该下一个节点加入堆中。
- 重复步骤2： 直到堆为空。
通过这种方式，我们每次都能确保将当前所有链表中的最小元素添加到结果链表，从而保证最终合并链表的有序性。
关键指针操作解析：head 与 last
在构建结果链表时，通常会使用一个虚拟头节点（dummy head）和两个指针：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: 42)。 执行 last.next = curr; 这行代码将 last 指向的节点的 next 字段设置为 curr。由于 head 和 last 最初指向同一个节点，因此 head 指向的节点的 next 字段也被更新了。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
接着执行 last = last.next; 这行代码将 last 指针向前移动，使其指向刚刚添加到链表中的新节点 curr。此时，head 仍然指向虚拟头节点，而 last 已经指向了结果链表的第一个实际节点。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
-
后续节点添加： 当循环继续，从堆中取出下一个最小节点 curr (例如 data: 50)。 执行 last.next = curr; 此时 last 指向的是 data: 42 的节点。这行代码将 data: 42 节点的 next 字段设置为 data: 50 的节点。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ data: 50 │ │ next: ─────────►│ next: ─────────►│ next: null │ └────────────┘ └────────────┘ └────────────┘
执行 last = last.next;last 指针再次向前移动，指向 data: 50 的节点。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ data: 50 │ │ next: ─────────►│ next: ─────────►│ next: null │ └────────────┘ └────────────┘ └────────────┘
整个过程中，head 始终保持指向最初的虚拟头节点。通过 head 我们可以访问到整个合并后的链表，而 last 则负责不断地在链表末尾追加新节点。最终，我们需要返回 head.next，因为虚拟头节点本身不包含有效数据。
Java 代码实现
以下是使用 Java 实现合并 K 个有序链表的完整代码示例。
import java.util.Comparator;
import java.util.PriorityQueue;
// 链表节点定义
class Node {
int data;
Node next;
Node(int key) {
data = key;
next = null;
}
}
// 节点比较器，用于最小堆
class NodeComparator implements Comparator {
@Override
public int compare(Node k1, Node k2) {
return Integer.compare(k1.data, k2.data); // 简化比较逻辑
}
}
class Solution {
/**
* 合并 K 个有序链表
* @param arr 包含 K 个链表头节点的数组
* @param K 链表的数量
* @return 合并后的有序链表的头节点
*/
public static Node mergeKList(Node[] arr, int K) {
// 使用优先级队列作为最小堆，并传入自定义比较器
PriorityQueue queue = new PriorityQueue<>(new NodeComparator());
// 创建一个虚拟头节点，简化结果链表的构建
Node head = new Node(0);
Node last = head; // last 指向当前结果链表的尾部
// 将所有 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();
// 将取出的节点添加到结果链表的尾部
last.next = curr;
last = last.next; // 移动 last 指针到新添加的节点
// 如果当前节点所属的链表还有后续节点，则将其加入堆中
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;
}
System.out.println();
}
public static void main(String[] args) {
int N = 3;
// 创建 K 个链表
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) {
System.out.print("合并后的链表: ");
printList(res); // 预期输出: 0 1 2 3 4 5 6 7 8 9 10 11
} else {
System.out.println("合并结果为空链表。");
}
}
} 代码详解
- Node 类： 定义了链表节点的基本结构，包含一个整型数据 data 和指向下一个节点的 next 指针。
-
NodeComparator 类： 实现了 Comparator
接口，用于自定义 Node 对象在 PriorityQueue 中的比较规则。这里是根据 data 字段进行升序比较，确保这是一个最小堆。 -
mergeKList(Node[] arr, int K) 方法：
-
PriorityQueue
queue = new PriorityQueue(new NodeComparator()); ：创建了一个优先级队列，它将作为我们的最小堆。 - Node head = new Node(0); Node last = head;：初始化虚拟头节点 head 和尾指针 last。
- for (int i = 0; i ：遍历输入链表数组，将每个链表的第一个节点（如果非空）添加到最小堆中。
-
while (!queue.isEmpty()) { ... }：主循环，只要堆不为空，就继续处理。
- Node curr = queue.poll();：从堆中取出当前所有链表头节点中的最小值。
- last.next = curr;：将取出的节点 curr 连接到结果链表的末尾。
- last = last.next;：将 last 指针移动到刚刚添加的 curr 节点，使其始终指向结果链表的当前尾部。
- if (curr.next != null) { queue.add(curr.next); }：如果 curr 节点所属的链表还有下一个节点，则将该下一个节点加入堆中，以便在后续迭代中进行比较。
- return head.next;：返回合并后链表的实际头节点（跳过虚拟头节点）。
-
PriorityQueue
- printList 和 main 方法： 用于辅助打印链表和演示如何使用 mergeKList 方法。
时间与空间复杂度
-
时间复杂度： 假设所有链表的总节点数为 N，每个链表平均有 N/K 个节点。堆中最多同时存在 K 个节点。
- 初始化：K 次 add 操作，每次 O(logK)。总计 O(K logK)。
- 主循环：N 次 poll 操作和最多 N 次 add 操作，每次 O(logK)。总计 O(N logK)。
- 因此，总时间复杂度为 O(N logK)。
- 空间复杂度： 优先级队列中最多存储 K 个节点，因此空间复杂度为 O(K)。
总结
通过使用最小堆（优先级队列）和巧妙的虚拟头节点与尾指针管理，我们可以高效地将 K 个有序链表合并成一个单一的有序链表。这种方法在处理大量链表时表现出良好的性能，是解决此类问题的标准方案。理解 head 和 last 指针的工作机制，特别是它们如何共同构建链表结构，是掌握此算法的关键。
