环形链表 II：从暴力到 Floyd 判圈法，AI 的直觉是如何「弯道超车」的？
读完本文你将了解环形链表 II 的三种解法演进 | 快慢指针Floyd 判圈法的核心原理 | 数学推导和面试应对策略— 题目原题给定一个链表的头节点 head判断链表中是否有环如果有环返回环的入口节点如果无环返回 null。项目说明输入head [3,2,0,-4], pos 1链表尾部指向索引 1 的节点形成环输出返回索引为 1 的节点值为 2约束链表中节点数范围 [0, 10⁴]-10⁵ ≤ Node.val ≤ 10⁵pos 为 -1 或有效索引 先问一个问题让 GPT 第一次写「环形链表入口检测」它会怎么写大多数人第一反应是哈希表。但面试官听完不会满意因为这道题真正的考点是 Floyd 判圈算法。 第一版AI 的朴素解法哈希表defdetectCycle(head): 暴力解法用集合记录访问过的节点 时间复杂度 O(n)空间复杂度 O(n) seenset()curheadwhilecur:ifcurinseen:returncur# 找到环入口seen.add(cur)curcur.nextreturnNone# 无环AI 几乎 100% 先写这个。面试官接下来会问「能不能不用额外空间」 AI 的自我优化优化链第 1 次优化快慢指针检测是否有环但不知道如何找入口第 2 次优化理解「相遇点 → 环入口」的数学关系最终版本完整 Floyd 算法时间 O(n)空间 O(1)哈希表O(n) 空间快慢指针检测有环/无环数学推导找入口节点Floyd 完整算法O(1) 空间☕ Java 实现publicclassSolution{publicListNodedetectCycle(ListNodehead){ListNodeslowhead;ListNodefasthead;booleanhasCyclefalse;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){hasCycletrue;break;}}if(!hasCycle)returnnull;ListNodeptrhead;while(ptr!slow){ptrptr.next;slowslow.next;}returnptr;}}为什么要加 JavaCSDN 第一大用户群体是 Java 开发者。链表题在面试中高频出现但 Java 指针操作比 Python 多了不少细节。两版代码摆在一起读者自己对比比你讲十句话都有用。 算法模式拆解模式Fast Slow Pointers快慢指针这道题不是「检测环」那么简单而是「找到环入口」。想象两个人在环形跑道上跑步。一个跑得快一个跑得慢。如果跑道是直的快的人永远跑在前面。但如果跑道是环形的快的人最终会「套圈」追上慢的人——这就是环检测的原理。核心数学关系面试考察重点设从 head 到环入口的距离为 a环的周长为 b。快慢指针在环中相遇时慢指针走了 s 步快指针走了 2s 步。由于快指针比慢指针多走了 n 圈n≥1有2s s n·b → s n·b所以慢指针走了 n 圈。从 head 到环入口的距离是 a从相遇点回到环入口的距离是 b - a。关键在于把 head 指针放回起点两个指针都每次走一步它们会在环入口相遇——因为 head 走 a 步到入口慢指针也从相遇点走了 a 步到达入口。a 步环中路径b-a 步head环入口 ✓相遇点模式变体LeetCode 141 环形链表 I只需检测是否有环LeetCode 287 寻找重复数数组转链表快慢指针找重复值LeetCode 202 快乐数数字序列是否进入循环️ 真实产品场景npm 包依赖的循环引用检测装一个 npm 包npm install跑了几分钟没结束最后报ELIFECYCLE错误。大概率是依赖图里出现了循环引用——A 依赖 BB 依赖 CC 又依赖 A。这和 Floyd 判圈算法解决的是同一个问题在依赖图中检测环找到环的入口。depends ondepends ondepends onpackage-apackage-bpackage-cnpm 的dedupe和hoisting算法本质上就是在依赖树中做环检测。✅ 面试官的点评通关标准哈希表解法O(n) 空间→ 通过不加分Floyd 判圈检测环 → 良好能解释第二阶段找入口的数学推导 → 优秀能说出为什么快指针走 2 步不是 3 步→ 加分项为什么快指针走 2 步不是 3 步如果快指针走 3 步步差为 2当环长 b 为奇数时它们可能永远无法在整数步相遇。步差为 1 保证相遇步数始终是整数。加分细节提到fast.next ! null的边界检查指出「检测环」和「找入口」是两个独立阶段举出真实场景npm 循环依赖、GC 中的循环引用检测 同类题推荐LeetCode 141 环形链表Easy前置简化版LeetCode 287 寻找重复数Medium数组转链表快慢指针找重复值面试高频LeetCode 202 快乐数Easy数字序列环检测来源说明✅ 已验证LeetCode 官方题解 AI 实测 来源Floyd’s Tortoise and Hare 算法Robert W. Floyd 于 1967 年提出
