本文详细阐述了如何使用最小堆（优先队列）高效合并 k 个已排序链表。重点解析了在链表构建过程中，虚拟头节点 `head` 和尾指针 `last` 协同工作的机制，特别是 `head` 如何通过 `last` 的 `next` 属性更新而间接累积节点，从而正确构建合并后的链表，避免了对 `head` 的直接赋值操作。
合并K个有序链表：基于最小堆的策略
合并K个有序链表是一个经典的算法问题，常见于数据结构和算法面试中。解决此问题的一种高效方法是利用最小堆（PriorityQueue），它能确保我们始终能从K个链表的当前头节点中，选出值最小的那个节点。
核心算法原理
该方法的核心思想是：
- 初始化最小堆：将所有K个链表的第一个节点（如果存在）加入到一个最小堆中。堆会根据节点的值进行排序，最小的节点总是在堆顶。
-
构建合并链表：
- 创建一个虚拟头节点（dummy head），用于简化链表构建过程。
- 循环从堆中取出最小节点。
- 将取出的节点连接到结果链表的末尾。
- 如果取出的节点还有下一个节点，则将其下一个节点加入堆中。
- 返回结果：当堆为空时，所有节点都已处理完毕，返回虚拟头节点的下一个节点，即为合并后的有序链表。
链表节点与比较器定义
首先，我们需要定义链表节点 Node 和一个用于 PriorityQueue 的比较器 NodeComparator。
class Node {
int data;
Node next;
Node(int key) {
data = key;
next = null;
}
}
// Class implements Comparator to compare Node data
class NodeComparator implements Comparator {
@Override
public int compare(Node k1, Node k2) {
if (k1.data > k2.data)
return 1;
else if (k1.data < k2.data)
return -1;
return 0;
}
} Node 类包含了节点的数据和指向下一个节点的引用。NodeComparator 则实现了 Comparator 接口，定义了如何比较两个 Node 对象，使其能够被 PriorityQueue 正确地作为最小堆使用。
mergeKList 函数实现详解
mergeKList 函数是实现合并逻辑的核心。
import java.util.Comparator;
import java.util.PriorityQueue;
class GFG {
// ... (Node and NodeComparator classes as defined above) ...
// Function to merge k sorted linked lists
static Node mergeKList(Node[] arr, int K) {
// Priority_queue 'queue' implemented
// as min heap with the help of
// 'compare' function
PriorityQueue queue = new PriorityQueue<>(new NodeComparator());
// 创建一个虚拟头节点，简化后续链表操作
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();
// 将当前最小节点连接到结果链表的末尾
last.next = curr;
// 更新 last 指针，使其指向新加入的节点
last = last.next;
// 如果当前节点还有下一个节点，将其加入队列
if (curr.next != null) {
queue.add(curr.next);
}
}
// 返回虚拟头节点的下一个节点，即为合并后的链表
return head.next;
}
// Print linked list
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;
// array to store head of linkedlist
Node[] a = new Node[N];
// Linkedlist1
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);
// Limkedlist2
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);
// Linkedlist3
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(); // Expected output: 0 1 2 3 4 5 6 7 8 9 10 11
}
} 指针机制深度解析：head 与 last 的协作
在 mergeKList 函数中，head 和 last 这两个指针的协同工作是理解链表构建的关键。许多初学者可能会疑惑，为什么 head 从未被直接赋值，最终却能指向完整的合并链表。
让我们逐步分析 head 和 last 的状态变化：
-
初始化：
Node head = new Node(0); // 创建一个虚拟头节点 Node last = head; // last 指针也指向这个虚拟头节点
此时，head 和 last 都引用同一个 Node 对象，我们称之为“虚拟头节点”。
head last ↓ ↓ ┌────────────┐ │ data: 0 │ │ next: null │ └────────────┘
-
第一次循环迭代：假设从优先队列中取出的第一个最小节点是 curr (例如，data = 0)。
Node curr = queue.poll(); // curr 引用到值为 0 的节点 (来自head3)
状态：
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 0 │ │ next: null │ │ next: null │ └────────────┘ └────────────┘
接下来执行：
last.next = curr;
这一步是关键！last 当前指向的是虚拟头节点。last.next = curr 实际上是修改了虚拟头节点的 next 属性，使其指向 curr 节点。因为 head 也引用着同一个虚拟头节点，所以 head.next 也被隐式地更新了。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 0 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
然后执行：
last = last.next;
last 指针现在移动到 curr 节点（也就是刚刚添加到链表末尾的节点）。注意，head 仍然指向最初的虚拟头节点，它并没有移动。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 0 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
如果 curr 节点还有下一个节点（例如 curr.next 引用值为 9 的节点），这个节点会被加入到优先队列中。
-
后续循环迭代：假设从优先队列中取出的下一个最小节点是 curr (例如，data = 1)。 此时 last 指向的是值为 0 的节点。
last.next = curr;
这会将值为 1 的节点连接到值为 0 的节点之后。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 0 │ │ data: 1 │ │ next: ─────────►│ next: ─────────►│ next: null │ └────────────┘ └────────────┘ └────────────┘ ^ 这里的 data:0 是虚拟头节点，第一个 data:0 是从队列中取出的第一个节点然后 last = last.next; 会将 last 移动到值为 1 的节点。
通过这种方式，last 指针不断向前推进，每次都将新的最小节点连接到当前 last 指向节点的 next 属性上。由于 head 始终保持指向最初的虚拟头节点，并且这个虚拟头节点的 next 属性是整个合并链表的起点，因此，当 last 完成所有节点的连接后，head.next 自然就构成了完整的合并链表。head 本身的值（0）是一个占位符，最终我们返回的是 head.next，从而排除了这个虚拟节点。
注意事项
- 虚拟头节点的作用：使用虚拟头节点（head = new Node(0)）极大地简化了链表操作。如果没有虚拟头节点，我们需要在第一个节点加入时进行特殊处理，判断结果链表是否为空。有了虚拟头节点，所有节点的添加逻辑都保持一致。
-
时间复杂度：假设总共有 N 个节点分布在 K 个链表中。每个节点最多会被插入和删除堆一次。堆操作的时间复杂度是 O(lo
gK)。因此，总的时间复杂度为 O(N logK)。
- 空间复杂度：优先队列中最多会存储 K 个节点（每个链表一个头节点）。因此，空间复杂度为 O(K)。
- Java PriorityQueue：Java 的 PriorityQueue 默认是最小堆。如果需要最大堆，可以通过传入自定义的 Comparator 来实现。
总结
利用最小堆合并K个有序链表是一种高效且优雅的解决方案。通过巧妙地使用虚拟头节点 head 和尾指针 last，我们能够以清晰的逻辑构建合并后的链表，避免了复杂的边界条件处理。深入理解 head 和 last 指针如何协同工作，对于掌握链表操作和面向对象编程中的引用概念至关重要。
