本文详细阐述了如何利用最小堆（优先队列）高效地合并k个已排序的链表。通过将每个链表的首节点加入最小堆，并循环提取最小元素、将其后继加入堆的策略，逐步构建合并后的有序链表。文章重点解析了在链表构建过程中，head和last指针如何协同工作，以及引入虚拟头节点（dummy head）的巧妙之处，确保结果链表的正确生成。
1. 合并K个有序链表问题概述
合并K个有序链表是一个经典的算法问题，常见于数据结构和算法面试中。其目标是将K个已经按升序排列的链表合并成一个单一的、同样按升序排列的链表。一种直观但效率不高的做法是两两合并，但这种方法的时间复杂度较高。更优的解决方案通常涉及使用优先队列（最小堆）。
2. 基于最小堆的解决方案
最小堆（PriorityQueue）提供了一种高效的方式来始终获取K个链表当前最小的元素。核心思想是：
- 将K个链表的第一个节点（如果存在）都加入到一个最小堆中。
- 每次从最小堆中取出最小的节点，将其添加到结果链表中。
- 如果被取出的节点还有下一个节点，则将其下一个节点加入到最小堆中。
- 重复步骤2和3，直到最小堆为空。
这种方法能够保证每次添加到结果链表中的元素都是当前所有链表头节点中的最小值，从而构建出整体有序的链表。
2.1 核心数据结构
为了实现上述算法，我们需要定义链表节点Node以及一个比较器NodeComparator，以便最小堆能够正确地比较Node对象。
立即学习“Java免费学习笔记（深入）”；
// 链表节点定义
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) {
if (k1.data > k2.data)
return 1;
else if (k1.data < k2.data)
return -1;
return 0;
}
} NodeComparator实现了Comparator接口，定义了如何比较两个Node对象，使得PriorityQueue能够按照节点中的data值进行升序排序（即形成最小堆）。
2.2 算法实现详解
以下是合并K个有序链表的Java实现代码：
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) {
if (k1.data > k2.data)
return 1;
else if (k1.data < k2.data)
return -1;
return 0;
}
}
class GFG {
// Function to merge k sorted linked lists
static Node mergeKList(Node[] arr, int K) {
// 使用NodeComparator创建最小堆
PriorityQueue queue = new PriorityQueue<>(new NodeComparator());
// 创建一个虚拟头节点（dummy head）
Node head = new Node(0);
// last指针指向当前结果链表的末尾，初始时与head指向同一个虚拟节点
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;
// 示例：创建3个有序链表
Node[] a = new Node[N];
// Linkedlist1: 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);
// Linkedlist2: 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);
// Linkedlist3: 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();
}
} 3. 理解head和last指针的协同工作
在链表构建过程中，head和last这两个指针的角色及其相互作用是理解代码的关键。
3.1 虚拟头节点（Dummy Head）的引入
代码中首先创建了一个虚拟头节点head = new Node(0);。这个节点本身不包含任何有效数据，其主要目的是简化链表操作，特别是当合并后的链表可能为空或者需要从头添加元素时。通过使用虚拟头节点，我们无需在每次添加第一个实际节点时进行特殊处理。
3.2 head和last的初始状态
紧接着，Node last = head;这行代码至关重要。它意味着last指针最初指向与head指针所指向的同一个虚拟节点。
我们可以将其想象为：
head last ↓ ↓ ┌────────────┐ │ data: 0 │ │ next: null │ └────────────┘
此时，head和last都指向这个值为0的虚拟节点。
3.3 循环中的指针更新机制
在while循环内部，每次从最小堆中取出一个节点curr（例如，curr节点的数据为42）：
-
last.next = curr;: 这行代码将curr节点连接到last指针当前所指向节点的next字段。由于last最初指向虚拟头节点，这一步实际上是将curr节点连接到了虚拟头节点的后面。
状态演变：
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
请注意，此时head仍然指向虚拟节点，但通过head.next已经可以访问到curr节点了。head本身没有被赋值新的节点，但它所指向的对象的内部结构（next字段）被修改了。
-
last = last.next;: 这行代码将last指针移动到刚刚添加的curr节点。现在，last指向结果链表的最新末尾，为下一次添加节点做准备。
状态演变：
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
这个过程会重复进行。每次循环，last.next = curr;都会在last当前指向的节点后面追加一个新节点，而last = last.next;则会更新last到这个新节点。由于head始终指向最初的虚拟节点，并且虚拟节点的next字段在每次追加时都被更新，所以head通过其next链条，间接地“积累”了所有后续添加的节点，最终形成了完整的合并链表。
例如，如果再添加一个数据为50的节点：
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ data: 50 │ │ next: ─────────►│ next: ─────────►│ next: null │ └────────────┘ └────────────┘ └────────────┘
3.4 返回结果
最终，当所有节点都已处理完毕，堆为空时，return head.next;将返回合并后的实际头节点。这样做是为了跳过我们最初创建的那个值为0的虚拟头节点，因为它只是一个辅助节点，不应包含在最终结果中。
4. 复杂度分析
- 时间复杂度： 假设总共有N个节点分布在K个链表中。每个节点都会被插入到最小堆一次，并从最小堆中取出一次。最小堆的插入和删除操作的时间复杂度是O(log K)，因为堆中最多同时存在K个元素（每个链表的当前头节点）。因此，总的时间复杂度为O(N log K)。
- 空间复杂度： 最小堆中最多会存储K个节点（每个链表一个）。因此，空间复杂度为O(K)。
5. 注意事项与总结
- 虚拟头节点的重要性：使用虚拟头节点极大地简化了链表构建逻辑，避免了在处理第一个实际节点时需要进行特殊判断。
- Comparator的正确实现：确保NodeComparator正确定义了节点数据的比较规则，以保证最小堆的正确性。
- 空链表处理：代码中通过if (arr[i] != null)和if (queue.isEmpty())有效地处理了空链表和所有链表都为空的情况。
- 泛用性：最小堆合并K个有序链表的思想不仅适用于链表，也可以应用于合并K个有序数组等类似问题。
通过上述分析，我们可以清楚地看到，head和last指针在构建合并链表时扮演着不同的角色：head作为结果链表的固定起点（通过其next指针），而last则是一个动态的“尾部追加器”，不断向前移动以连接新的节点。这种协作方式是链表操作中常见的模式，理解它对于掌握链表算法至关重要。
