本文详解单链表检测与移除环的完整实现，重点解决当环从头节点开始时因 `prev` 为 `null` 导致的空指针异常，并提供健壮、通用的修复方案。
在使用 Floyd 判圈算法（快慢指针）检测并移除链表环时，一个常见却容易被忽视的问题是：当环的入口恰好是头节点（即 Head 自身位于环中，如 tail.next = Head）时，标准的“找前驱并断开”逻辑会失败——因为此时快慢指针首次相遇后，重新从头出发同步移动时，prev 可能始终未被赋值，最终为 null，导致 prev.next = null 抛出 NullPointerException。
根本原因在于原算法中 prev 的初始化和更新逻辑依赖于 slow != fast 循环至少执行一次。但当环入口是头节点时，重置后的 slow = Head 与 fast（已在环中某点）可能初始即相等，导致 while(slow != fast) 循环体完全跳过，prev 保持 null。
✅ 正确解法：引入虚拟头节点（dummy node）
通过在原链表前插入一个不参与业务逻辑的哨兵节点，将问题统一转化为「环入口非 dummy」的情形，从而保证 prev 必然被正确赋值。该技巧不改变时间/空间复杂度（仍为 O(n) 时间、O(1) 额外空间），且完全兼容所有环位置（包括头节点成环、中间成环、自环等）。
以下是修正后的完整可运行代码：
public class LoopsRemove {
public static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public static Node Head;
public static int count = 0;
public static int removeCycle() {
// ✅ 关键修复：添加 dummy 节点，避免 head 成环时 prev 为 null
Node dummy = new Node(0);
dummy.next = Head;
Node slow = dummy;
Node fast = dummy;
boolean hasCycle = false;
// 第一阶段：检测环是否存在
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
if (!hasCycle) {
return 0; // 无环
}
// 第二阶段：定位环入口，并找到其前驱节点
slow = dummy;
Node prev = null;
while (slow != fast) {
prev = fast; // prev 始终跟踪 fast 的上一节点
slow = slow.next;
fast = fast.next;
}
// ✅ 此时 prev 必为环入口节点的前驱（在 dummy 链表中）
prev.next = null; // 断开环
return 1;
}
public static void main(String[] args) {
// 构造带环链表：3 → 4 → 5 → 6 → 3（环入口为 Head）
Head = new Node(3);
Head.next = new Node(4);
Head.next.next = new Node(5);
Head.next.next.next = new Node(6);
Head.next.next.next.next = Head; // 形成环
System.out.println(removeCycle()); // 输出: 1
// ✅ 安全验证：打印最后一个节点的 next（应为 null）
System.out.println(Head.next.next.next.next); // 输出: null
}
}? 关键注意事项：
- 不要尝试访问 null.next.data（如原代码 Head.next.next.next.next.data），这必然抛异常；应直接打印引用本身（如 System.out.println(node.next)）来验证是否为 null。
- dummy 仅在 removeCycle() 方法内有效，方法返回后即不可达，会被 JVM 自动垃圾回收，无内存泄漏风险。
- 该方案保持了原算法的简洁性与高效性，无需额外遍历或哈希表，是工业级链表环处理的标准实践之一。
通过引入虚拟头节点，我们优雅地规避了边界条件陷阱，使环检测与移除逻辑真正具备鲁棒性与普适性。
