如何正确移除单链表中的环（包括头节点成环的情况）_网络技术

本文详解单链表检测与移除环的完整实现，重点解决当环从头节点开始时因 `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 自动垃圾回收，无内存泄漏风险。
该方案保持了原算法的简洁性与高效性，无需额外遍历或哈希表，是工业级链表环处理的标准实践之一。

通过引入虚拟头节点，我们优雅地规避了边界条件陷阱，使环检测与移除逻辑真正具备鲁棒性与普适性。

# node # ai # jvm # NULL # while # 循环 # 指针 # 空指针 # 算法 # 链表 # 环中 # 移除 # 首次 # 遍历 # 上一 # 问题是 # 可达 # 已在 # 一转

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】