本文详解单链表环检测与断环的完整实现，重点解决当环起点为头节点时因prev未初始化导致的nullpointerexception问题，并提供带哨兵节点的安全修复方案。
在Java中实现单链表环的检测与移除，核心算法基于Floyd判圈法（快慢指针），但其标准变种在处理“环起点即为头节点”的边界情况时存在致命缺陷：当slow与fast首次相遇于Head时，后续的prev追踪逻辑会因prev始终为null而触发NullPointerException——这正是原代码在第44行 prev.next = null 处崩溃的根本原因。
问题本质在于：当环从头节点开始（即Head本身是环入口），在第二阶段寻找环入口点的同步移动过程中，slow与fast从起点出发即相等（slow == fast == Head），导致while(slow != fast)循环体一次都不执行，prev保持初始值null，最终解引用失败。
✅ 正确解法：引入虚拟头节点（Dummy Node）
通过在原链表前插入一个不参与业务逻辑的哨兵节点，将问题统一转化为“环入口非首节点”的通用情形，从而保证第二阶段循环至少执行一次，使prev被正确赋值：
public static int removeCycle() {
// 创建哨兵节点，指向原Head，扩展链表长度
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指向环入口节点的前驱，断开环
prev.next = null;
return 1;
}⚠️ 关键注意事项：
-
主函数调用需同步修正：断环后，原循环尾节点的next已置为null，不应再访问其data字段（否则NPE）。应改为打印该引用本身以验证是否为null：
System.out.println(removeCycle()); // 输出: 1 System.out.println(Head.next.next.next.next); // 输出: null ✅
- 内存安全：dummy为局部变量，方法结束后自动脱离作用域，其所指向的节点将被JVM垃圾回收器自动清理，无需手动干预。
- 时间复杂度：O(n)，空间复杂度：O(1)，符合链表原地操作的最佳实践。
该方案不仅修复了头节点成环的边界缺陷，还保持了算法简洁性与高效性，是生产环境中推荐的标准实现模式。
立即学习“Java免费学习笔记（深入）”；
