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

简化版

用快慢指针（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。
相交链表：两个链表是否相交、求交点，也是快慢/双指针的思路变体。

这节要真正讲透，需要把结论落到结构变化上：在如何判断链表是否有环？环的入口怎么找？里，每一步操作都会影响某个指针、索引、节点关系或辅助状态。可以主动说明“操作前满足什么不变量、操作后这个不变量如何继续成立”，再补一个 3 个节点或 5 个元素的小例子。这样读者不仅知道答案，还能自己推导同类变体。

五、方法对比与具体例子

方法	判断有环	找入口	时间	额外空间
哈希表	访问到重复节点即有环	第一个重复节点就是入口	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 快慢指针。

八、一步步推演与边界

回答如何判断链表是否有环？环的入口怎么找？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

补充边界演练

为了把如何判断链表是否有环？环的入口怎么找？真正讲透，可以再补一组边界演练。第一组是空结构或空输入，用来确认代码不会在访问 head、root、stack top 或队首时崩溃；第二组是单元素，用来确认循环条件不会多走一步；第三组是 2～3 个元素的最小非平凡样例，用来观察指针、栈、队列或 visited 状态如何变化。

如果是树遍历题，就画出 root、left、right 三个节点，逐步记录栈里元素的进出；如果是图遍历题，就用 4 个点、4 条边验证 BFS 的层次性和 DFS 的路径性；如果是链表题，就把 pre、cur、next 三个指针写在纸上，每移动一次都检查链是否断开。面试时把这个过程讲出来，比单纯写出最终代码更能说明你真的理解结构变化。

边界 1：空输入 -> 直接返回，不访问节点属性
边界 2：单元素 -> 循环最多处理 1 次，结果保持合法
边界 3：三个元素 -> 手动跟踪每一步状态变化
验证目标：不变量始终成立，且每个节点/元素被处理次数可解释

七、加强记忆

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

简化版

详细版