如何在 Java 中利用数组实现简单的环形链表检测（快慢指针法）逻辑建模

Ja va中可用数组模拟链表并用快慢指针检测环：以next[i]表示节点i的后继索引，slow每次移1步、fast每次移2步，若相遇则有环，若越界则无环。

直接说结论：在Ja va里，虽然没法用数组造出一个真正的链表对象，但完全可以用数组来模拟链表的逻辑结构，再套用经典的快慢指针法来检测环。这其中的关键，在于把数组当成一个“节点池”，用数组元素的值来代表“下一个节点去哪儿找”，从而在逻辑上构建出一条单向链表。之后，在这条逻辑链上跑一遍弗洛伊德判圈算法，问题就解决了。

用数组模拟链表结构

怎么模拟呢？假设我们有一个整型数组 int[] next。这里的 next[i] 存储的值，就代表了从节点 i 出发，下一个节点的索引位置。举个例子就明白了：

• 如果 next = {1, 2, 3, 4, 2}，那它表示的逻辑链路就是：0→1→2→3→4→2→3→4→… 看，从节点4又指回了节点2，这就形成了一个环（2→3→4→2）。
• 这里有个前提：所有索引值都必须在合法范围内，也就是0到 next.length - 1。如果某个 next[i] 的值小于0，或者超出了数组边界，那通常就认为链表到这里终止了，相当于一个空指针，代表没有环。

快慢指针在数组上的实现逻辑

逻辑结构搭好了，接下来就是让快慢指针在上面“跑”起来。定义两个整型变量作为“游标”：slow（慢指针，每次走1步）和 fast（快指针，每次走2步）。它们都从给定的起始索引（比如0）出发：

• 慢指针走一步：slow = next[slow]
• 快指针走两步：fast = next[next[fast]]（这里要小心，必须确保中间那一步也不越界，否则可以直接判定无环）
• 如果某一步发现 slow == fast，并且它们都处于有效索引位置，那就恭喜你——指针相遇，环被检测出来了。
• 反之，如果任何一个指针在移动过程中“掉出了”数组边界（即索引无效），那就说明链表有终点，不存在环。

完整可运行示例代码

道理讲清楚了，来看一段更健壮的实现代码。这段代码考虑了各种边界情况，比如空数组、非法起始点，以及在移动过程中步步为营的越界检查：

public static boolean hasCycle(int[] next, int start) {
    if (next == null || start < 0 || start >= next.length) return false;
    int slow = start, fast = start;
    while (true) {
        // slow 走一步
        slow = next[slow];
        if (slow < 0 || slow >= next.length) return false; // 走到头了，无环
        // fast 走两步（必须分步检查，防止中间步越界）
        int mid = next[fast];
        if (mid < 0 || mid >= next.length) return false;
        fast = next[mid];
        if (fast < 0 || fast >= next.length) return false;
        if (slow == fast) return true; // 相遇，有环
    }
}

想深入掌握Ja va？立即学习“Ja va免费学习笔记（深入）”。

注意事项与常见陷阱

方法虽巧妙，但在实际使用时，有几个细节绝对不能忽略：

• 数组语义必须明确：这个数组必须代表一个确定的单向映射，也就是说，每个索引位置最多只能有一个“出边”。这符合链表的定义，不能出现一个节点指向多个下一个节点的情况。
• 起始点不唯一：链表（或者说这个图结构）的入口不一定就是0。如果存在多个独立的链（比如一个“森林”），就需要对每个尚未访问的起点单独调用检测方法。
• 功能局限：这个方法只负责回答“有没有环”这个问题。如果你还需要找到环的入口点，可以在快慢指针相遇后，将慢指针重置回起点，然后让两个指针都以每次一步的速度前进，它们再次相遇的地方就是环的入口。
• 严防死循环：这是最关键的一点。在通过索引访问数组元素之前，务必先校验该索引的有效性，否则一旦数组内容有误，程序就可能陷入无限循环或者直接抛出数组越界异常。