如何判断链表是否有环？环的入口怎么找？

简化版

用快慢指针（Floyd 判圈）：慢指针一次走 1 步、快指针一次走 2 步。有环的话两者必然相遇；无环则快指针先到达 null。找入口：相遇后让一个指针回到头，两个指针都每次走 1 步，再次相遇处就是环的入口。时间 O(n)、空间 O(1)。

详细版

判断是否有环：

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;        // 走 1 步
        fast = fast.next.next;   // 走 2 步
        if (slow == fast) return true; // 相遇 → 有环
    }
    return false; // fast 到达 null → 无环
}

找环入口：

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {          // 第一次相遇
            ListNode p = head;
            while (p != slow) {      // 一个从头走，一个从相遇点走
                p = p.next;
                slow = slow.next;
            }
            return p;                // 相遇点即入口
        }
    }
    return null;
}

也可以用哈希表记录访问过的节点，第一个重复出现的就是入口，但那是 O(n) 空间。快慢指针的 O(1) 空间是标准答案。

完整版教学

一、为什么快慢指针一定会相遇

把有环链表想成一条跑道：慢指针跑得慢、快指针跑得快，两者都进了环之后，就是在一个圆环上追及。快指针每轮比慢指针多走 1 步，相对距离每轮缩小 1，环长有限，所以一定会追上（差距减到 0 就是相遇），绝不会「跨过去错开」。而如果无环，快指针会先冲到链表末尾的 null，循环退出。

二、找入口的数学推导（一步不虚）

设：头到环入口距离为 a，环入口到相遇点距离为 b，环长为 L（相遇点再走 L−b 回到入口）。

相遇时：慢走了 a + b，快走了 a + b + n·L（快在环里多绕了 n 圈）。又因为快是慢的 2 倍：

2(a + b) = a + b + n·L
⟹ a + b = n·L
⟹ a = n·L − b = (n−1)·L + (L − b)

L − b 正是「从相遇点再走到入口的距离」。所以：一个指针从头走 a 步、另一个从相遇点走 (n−1)·L + (L−b) 步，都会停在入口。让两个指针都每次走 1 步，它们会在入口相遇。这就是「相遇后一个回头、同速再走」能找到入口的原因。

三、边界与易错点

循环条件必须是 fast != null && fast.next != null，两个都要判，否则 fast.next.next 会空指针。
快慢指针都从 head 出发；有的写法慢从 head、快从 head.next，那套的相遇判断和入口逻辑会不同，别混用。
只问「有没有环」时，不需要找入口那段。

四、能顺带解决的问题

环的长度：相遇后让一个指针停着，另一个继续走，再回到相遇点走过的步数就是环长 L。
相交链表：两个链表是否相交、求交点，也是快慢/双指针的思路变体。

五、方法对比与具体例子

方法	判断有环	找入口	时间	额外空间
哈希表	访问到重复节点即有环	第一个重复节点就是入口	O(n)	O(n)
快慢指针	快慢相遇即有环	相遇后头指针与相遇指针同速走	O(n)	O(1)

举个具体例子：链表 1→2→3→4→5，且 5.next 指回 3，则 a=2（头到入口 3 之前走 2 步），环长 L=3。快慢指针第一次可能在环内某点相遇；相遇后让一个指针回到 1，另一个留在相遇点，同速前进，前者走 2 步到 3，后者也会绕到 3，入口自然被定位出来。

判环题的核心不是“快指针跑得快”，而是“进入环后相对速度为 1，有限环上必追及；入口定位靠距离等式对齐”。

六、常见误区与追问

误区：快指针可能每次都跳过慢指针，所以不一定相遇。 在环内看相对距离，快指针每轮比慢指针多 1 步，相对距离按 1 递减取模，必然会变成 0。
误区：相遇点就是环入口。 第一次相遇点通常只是环内某点，必须再用一个指针从头出发同速走，第二次相遇才是入口。
误区：判断条件只写 fast != null 就够了。 代码要访问 fast.next.next，所以必须同时保证 fast != null && fast.next != null。
追问：如何求环长？ 第一次相遇后固定一个指针，另一个继续走到再次回到相遇点，走过的步数就是环长。
追问：如果只要求判断有环，需要入口推导吗？ 不需要，快慢指针相遇即可返回 true；入口推导是 detectCycle 的扩展。
追问：哈希表法什么时候可以说？ 可以作为直观方案或调试思路，但面试标准优化答案应给出 O(1) 空间的 Floyd 快慢指针。

七、加强记忆

判环用快慢指针「快 2 慢 1，相遇即有环，到 null 即无环」；找入口靠 a = n·L − b 这个关系——相遇后一个指针回到头，两指针同速再走，相遇点就是入口。全程 O(1) 空间。

简化版

详细版