本文详细阐述了如何利用最小堆（PriorityQueue）高效地合并K个已排序的链表。重点聚焦于算法实现中的关键指针操作，特别是`head`和`last`这两个节点引用如何协同工作来构建最终的合并链表。通过逐步分析代码逻辑和指针状态变化，揭示了`head`节点如何通过`last`指针的间接操作而“被填充”，最终形成一个完整的有序链表，并提供了完整的Java示例代码及注意事项。
使用最小堆合并K个有序链表
合并K个已排序的链表是一个经典的算法问题，常见于数据结构与算法面试中。其目标是将K个独立的、内部已排序的链表合并成一个单一的、完全排序的链表。解决此问题的一种高效方法是利用最小堆（Min-Heap），也称为优先队列（PriorityQueue）。
问题背景与最小堆方案
假设我们有K个链表，每个链表都已按升序排列。我们需要将它们合并成一个新的链表，新链表也应按升序排列。
暴力方法可能是两两合并，但这会导致效率低下。使用最小堆的策略是：
- 将K个链表的头节点全部放入一个最小堆中。
- 每次从堆中取出最小的元素（即堆顶元素）。
- 将取出的元素添加到结果链表的末尾。
- 如果取出的元素所属的链表还有下一个节点，则将该下一个节点重新放入堆中。
- 重复步骤2-4，直到堆为空。
这种方法确保了每次添加到结果链表的都是当前所有链表头节点中的最小值，从而保证了最终合并链表的有序性。
核心数据结构：Node与NodeComparator
在Java中实现链表节点通常定义一个Node类，包含数据和指向下一个节点的引用。为了使PriorityQueue能够正确地将Node对象作为元素并按其data字段进行排序，我们需要提供一个Comparator。
// 链表节点定义
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接口，其compare方法根据两个Node的data值进行比较，返回1、-1或0，以实现升序排序（最小堆）。
mergeKList函数详解
核心逻辑封装在mergeKList函数中。我们将逐步解析其实现细节，特别是head和last指针的巧妙运用。
class GFG {
// Function to merge k sorted linked lists
static Node mergeKList(Node[] arr, int K) {
// 1. 初始化最小堆
PriorityQueue queue = new PriorityQueue<>(new NodeComparator());
// 2. 初始化结果链表的虚拟头节点和尾指针
Node head = new Node(0); // 虚拟头节点，其数据值不重要
Node last = head; // last指针初始指向head
// 3. 将所有K个链表的头节点入堆
for (int i = 0; i < K; i++) {
if (arr[i] != null) {
queue.add(arr[i]);
}
}
// 处理K=0或所有链表为空的情况
if (queue.isEmpty())
return null;
// 4. 主循环：从堆中取出元素并构建结果链表
while (!queue.isEmpty()) {
Node curr = queue.poll(); // 取出堆顶（最小）元素
last.next = curr; // 将curr连接到结果链表的末尾
last = last.next; // 移动last指针到新添加的节点
// 如果curr节点所属的链表还有后续节点，则将其入堆
if (curr.next != null) {
queue.add(curr.next);
}
}
// 5. 返回结果链表的实际头节点
return head.next;
}
// ... (printList 和 main 方法省略，见完整代码)
} 初始化：理解head与last指针
这是理解代码如何构建链表的关键部分。
Node head = new Node(0); // 虚拟头节点 Node last = head; // last指针初始指向head
这里创建了一个虚拟头节点head。它的data值（例如0）并不重要，因为这个节点最终不会包含在返回的合并链表中。head的主要作用是提供一个固定的起点，方便后续操作。 last指针被初始化为指向head。这意味着head和last在内存中引用的是同一个Node对象。
我们可以这样形象地表示初始状态：
head last ↓ ↓ ┌────────────┐ │ data: 0 │ │ next: null │ └────────────┘
合并过程：主循环逻辑
while (!queue.isEmpty())循环是构建合并链表的核心。每次迭代都会从堆中取出当前所有链表头节点中的最小元素，并将其添加到结果链表。
-
取出最小元素：
Node curr = queue.poll();
curr现在引用了堆中最小的那个节点。假设curr的data是42。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ next: null │ │ next: null │ └────────────┘ └────────────┘
-
连接到结果链表：
last.next = curr;
这一步至关重要。last当前指向的是虚拟头节点head。执行last.next = curr时，实际上是修改了head节点的next指针，使其指向curr。此时，head节点已通过last指针的间接操作，成功“接收”了第一个实际数据节点。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
可以看到，head节点现在通过其next指针连接到了curr节点。
-
更新last指针：
last = last.next;
last指针现在移动到刚刚添加的curr节点。这是为了在下一次循环中，新的最小元素能被连接到当前结果链表的末尾。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ next: ─────────►│ next: null │ └────────────┘ └────────────┘
如果循环继续，新的节点（例如data为50）会被添加到last的next，然后last会再次移动。
head last curr ↓ ↓ ↓ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ data: 0 │ │ data: 42 │ │ data: 50 │ │ next: ─────────►│ next: ─────────►│ next: null │ └────────────┘ └────────────┘ └────────────┘
通过这种机制，head始终保持对链表第一个（虚拟）节点的引用，而last则不断向后移动，负责在链表末尾追加新节点。最终，head.next将指向合并链表的第一个实际数据节点。
-
将下一个元素入堆：
if (curr.next != null) { queue.add(curr.next); }如果当前取出的curr节点所属的原始链表还有后续节点，则将该后续节点重新放入堆中，以便在后续迭代中继续参与最小值的选择。
返回结果
return head.next;
由于head是一个虚拟头节点，它本身不包含有效数据。因此，我们返回head.next，这正是合并后链表的第一个实际数据节点。
完整示例代码
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) {
// Priority_queue 'queue' implemented
// as min heap with the help of
// 'compare' function
PriorityQueue queue
= new PriorityQueue<>(new NodeComparator());
// Node at[] = new Node[K]; // 此行在原代码中未被使用，可移除
Node head = new Node(0); // 虚拟头节点
Node last = head; // last指针初始指向head
// Push the head nodes of all
// the k lists in 'queue'
for (int i = 0; i < K; i++) {
if (arr[i] != null) {
queue.add(arr[i]);
}
}
// Handles the case when k = 0
// or lists have no elements in them
if (queue.isEmpty())
return null;
// Loop till 'queue' is not empty
while (!queue.isEmpty()) {
// Get the top element of 'queue'
Node curr = queue.poll();
// Add the top element of 'queue'
// to the resultant merged list
last.next = curr;
last = last.next;
// Check if there is a node
// next to the 'top' node
// in the list of which 'top'
// node is a member
if (curr.next != null) {
// Push the next node of top node
// in 'queue'
queue.add(curr.next);
}
}
// Address of head node of the required
// merged list
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; // K个链表
// array to store head of linkedlist
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(); // 输出: 0 1 2 3 4 5 6 7 8 9 10 11
}
} 关键点与注意事项
- 虚拟头节点的作用： head节点是一个虚拟节点，它的主要目的是简化代码逻辑。如果没有这个虚拟头节点，在第一次添加元素时，我们需要特殊处理head的赋值，并确保last也正确初始化。使用虚拟头节点，所有节点的添加操作都可以统一通过last.next = curr; last = last.next;来完成，避免了对空链表的特殊判断。
- head和last的引用关系： 理解Node last = head;意味着last和head最初指向同一个Node对象。当last.next = curr;执行时，它修改的是head所指向的那个对象的next字段。之后last = last.next;使last指向了新添加的节点，而head仍然指向最初的虚拟节点，但其next指针已经更新，从而间接构建了链表。
- 时间复杂度： 假设总共有N个节点分布在K个链表中。每次从堆中取出元素和放入元素的时间复杂度是O(logK)。由于每个节点都会被取出和放入堆一次，所以总的时间复杂度是O(N logK)。
- 空间复杂度： 最小堆中最多会存储K个节点（每个链表的当前头节点），因此空间复杂度是O(K)。
总结
通过最小堆合并K个有序链表是一种高效且优雅的解决方案。核心在于利用优先队列维护当前所有链表头部的最小值，并逐步构建结果链表。对head虚拟节点和last尾指针的理解是掌握此算法实现的关键，它简化了链表的构建过程，避免了对链表头部的特殊处理。这种模式在处理链表问题时非常常见且实用。
