本文详细阐述了如何使用最小堆（优先队列）高效合并 k 个已排序链表。重点解析了在链表构建过程中，虚拟头节点 `head` 和尾指针 `last` 协同工作的机制，特别是 `head` 如何通过 `last` 的 `next` 属性更新而间接累积节点，从而正确构建合并后的链表，避免了对 `head` 的直接赋值操作。
合并K个有序链表是一个经典的算法问题，常见于数据结构和算法面试中。解决此问题的一种高效方法是利用最小堆（PriorityQueue），它能确保我们始终能从K个链表的当前头节点中，选出值最小的那个节点。
该方法的核心思想是：
首先，我们需要定义链表节点 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<Node> {
@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 正确地作为最小堆使用。
立即学习“Java免费学习笔记（深入）”；
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<Node> 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
}
}在 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，从而排除了这个虚拟节点。
利用最小堆合并K个有序链表是一种高效且优雅的解决方案。通过巧妙地使用虚拟头节点 head 和尾指针 last，我们能够以清晰的逻辑构建合并后的链表，避免了复杂的边界条件处理。深入理解 head 和 last 指针如何协同工作，对于掌握链表操作和面向对象编程中的引用概念至关重要。
以上就是Java中利用最小堆合并K个有序链表及其头尾指针机制解析的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
814
收藏
