1. 题目解析环的定义、边界形态与应用场景作为链表类问题里最经典的入门题之一环形链表I考查的并不仅仅是你会不会写一个 while 循环而是你有没有理解指针移动背后那条追及问题的逻辑链条。题目说起来特别简单给定一个链表的头节点 head判断链表是否存在环。可就是这道题在面试中能延伸出环入口定位、环长计算、算法正确性证明等一系列问题。这篇文章就把这条主线完整梳理一遍。先把这个题目拆到最干净。判环的定义是链表中某个节点的 next 指针指向了链表中前面已经出现过的节点这就形成一个环。换句话说只要从某个节点出发顺着 next 一直走能走回到自己头上那就有环。这个定义里有个容易被忽略的细节环不一定是从头节点的某个位置才开始的。它可能很小比如只有两个节点互相指也可能很大比如一万个节点的链表最后一个节点的 next 指回第五百个节点甚至极端到只有一个节点它自己指向自己。输入链表也可能直接是空链表。这些边界情况都会在判定时给你找麻烦。从实际应用的角度看判环为什么值得专门考一道题因为现实系统里有大量链表形态的结构。举个最典型的例子一个内存池里的空闲块如果因为指针被错误改写而形成了环路分配器就可能在同一批块里无限打转再比如某些状态机或任务调度链一旦某个回调注册成了环程序就表现为看起来在运行实际上永远跑不完。判环的思想在死锁检测、路由环路防御、编译器控制流分析里都有直接或间接的对应。所以面试官问这道题说是考算法其实也在考你有没有在一个可能有问题的链式结构里快速定位异常的工程直觉。这个系列在在线评测平台上分 I 和 II。I 只要求你回答有没有环能输出布尔值即可II 则进一步要求你把环的入口节点找出来。很多人的误区是把 I 当作 II 的简化版只背一个解法就完事。但事实上 I 才是核心II 的所有推导都建立在 I 的相遇结论之上。只有把 I 的每一步推演吃透后面遇到入口定位、环长计算、正确性证明才不会心虚。1.1 三种输入形态无环、有环、自环为了方便后续讨论先把链表能出现的形态归一下类无环链表每个节点最多被访问一次遍历到 None 结束这是最普通的情况。有环链表某个节点的 next 指回之前出现过的节点遍历永远不会自然停止。入口节点可能离头节点很远环也可能很长。自环单个节点的 next 指向自身这是环的最简形态也是面试写代码时最容易漏判的一种。判定时真正要处理的无非三类空链表、单节点无环、单节点自环。空链表和单节点无环都直接返回 false单节点自环必须返回 true。这个看起来很基础的边界恰恰是哈希表解法和快慢指针解法都必须单独照顾的地方。很多人写完代码只测了普通用例觉得能跑通就提交了结果在自环上栽了跟头。2. 暴力解法的价值哈希表思路、实现与它的天花板先别急着上快慢指针。如果你第一次见到这道题最自然的想法其实是哈希表沿着链表走每经过一个节点就把它记下来如果走到某个节点时发现它已经在记录里说明有环如果走到尾部的 None说明没环。这个思路完全正确也几乎不可能写错所以它天然适合作为第一版答案。2.1 哈希表解法的代码与复杂度Python 写出来是这样def has_cycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return FalseJava 版本大同小异用 HashSetpublic boolean hasCycle(ListNode head) { SetListNode seen new HashSet(); for (ListNode cur head; cur ! null; cur cur.next) { if (!seen.add(cur)) { return true; } } return false; }有个实现细节值得一说Java 里直接用!seen.add(cur)作为判断利用的是 Set.add 返回值的语义——元素已存在时返回 false。这样既完成了去重判断又完成了插入省了一行代码。但如果你觉得这样可读性差拆成 contains 加 add 两步也完全没问题。我个人在面试时倾向写得更直白因为面试官更在意你的思路而不是这种小聪明。时间复杂度和空间复杂度都是 O(n)。哈希表方案在数据量小时没有任何问题但它有两个硬伤一是空间开销在链表很长时会成为瓶颈二是在面试中这道题的标准追问就是能不能用 O(1) 空间如果你只答出哈希表后面基本是被牵着走。所以哈希表更像是热身它最大的价值是让你确认自己对题意的理解没有偏差同时给了你后续比较的基准。2.2 哈希表方案在工程场景里的隐性成本更进一步说哈希表判环在真实系统里还有个容易忽略的成本它需要一套区分节点的手段。如果是链表节点这种引用类型Java 里默认的 hashCode 基于对象地址通常没问题但如果节点是自定义结构且没有正确实现 hashCode 和 equals就可能引入新的 bug。而快慢指针方案不依赖任何哈希、不依赖节点是否支持相等判断只需要能沿着 next 移动适用范围更广。这也是为什么底层编译器分析、网络报文环检测这类场景更倾向用指针类的 Floyd 算法而不是哈希集合。理解这一点你在面试时说选择快慢指针的原因就会比单纯说空间更优更有说服力。3. Floyd判圈算法快慢指针为什么必然相遇Floyd 判圈算法是这道题的标准解也叫龟兔赛跑算法。思路极其简单两个指针slow 每次走一步fast 每次走两步同时从头节点出发。如果链表无环fast 会先撞到 None直接结束如果有环slow 和 fast 最终一定会在环内相遇。这个算法最反直觉的地方在于fast 每次走两步它难道不会跳过slow 吗比如两个指针在环上相邻fast 两步跨过去不正好和 slow 错开这是绝大多数人第一次接触时都会有的疑问。答案是不会因为环是一个闭合的圆形轨道所谓跳过在圆形轨道上只意味着两者的相对位置发生了变化而不是真的擦肩而过。关键在于相对速度每过一个单位时间slow 前进 1fast 前进 2所以 fast 相对 slow 前进了 1。在环形轨道上一个以速度 1 逼近的追及者无论初始距离是多少最终都必然追上——除非距离无限大但环的长度是有限的。3.1 用追及模型证明为什么相遇是必然事件严谨一点设头节点到环入口的距离为 X环长为 L相遇点距离环入口沿前进方向为 Y。slow 从入口出发走到相遇点一共走了 Y 步。这里有个关键前提相遇发生在 slow 进入环后的第一圈之内。为什么因为 fast 相对 slow 的速度是 1当 slow 刚到环入口时fast 已经在环内某个位置两者之间的弧长差距最大也只有 L-1所以追上所需的时间最多 L-1 步。在这段时间里 slow 只前进了 L-1 步不可能完成整整一圈。这个结论一定要记牢后面推导环入口时会反复用到。于是相遇时slow 的总路程是 X Yfast 的总路程是 X Y m*Lm 是 fast 在环内多跑的整圈数m ≥ 1。由于 fast 速度是 slow 的两倍总路程也是两倍2(X Y) X Y m*L X Y m*L X m*L - Y这个式子的含义是头节点到环入口的距离 X等于 m 圈环长减去入口到相遇点的距离 Y。也就是说从相遇点再往前走 Y 步就会回到入口而从 head 出发走 X 步也会到达入口两者之间的差正好是环长的整数倍。我最早学这个证明的时候总觉得m*L - Y这个形式不太直观后来换了个角度就通了把相遇点想象成环形跑道上的一个标记把链表从相遇点剪开你会得到一条长度为 X Y 的直线段而它正好等于若干整圈。只要两者相距整数圈你从任何一个位置同时出发、同速前进就必然在同一位置碰上。这个类比让我再也不容易忘记入口推导的结论。3.2 代码实现与复杂度分析def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False要点有两个。第一while 条件必须写成fast and fast.next顺序不能换。因为 fast 要移动两步必须先确认当前节点非空再确认下一个节点非空否则在访问fast.next.next时可能抛空指针异常。第二相遇判断放在每次快指针移动之后不要放在最前面否则初始状态下 slow 和 fast 都指向 head一上来就会误判成环。时间复杂度的最坏情况怎么估教科书上常写 O(n)但很多初学者会疑惑fast 可能在环里绕很多圈为什么整体还是 O(n)关键在这里无环部分最多走 X 步一旦进入环内fast 追上 slow 至多需要 L-1 步。所以总步数是 X O(L)而 X L 正是链表的规模于是整体是 O(n)。空间复杂度自然是 O(1)这也是它相比哈希表方案最大的优势。4. 从有没有环到环的入口在哪一步之遥的进阶推导141 只问有没有环但几乎每个面试官都会在你讲完 Floyd 解法后追问一句那你能找到环的入口节点吗这就是环形链表II。好消息是答案不需要新算法只需要在相遇后多做一个小操作。结论先放在这里在第一次相遇点把其中一个指针重新移回 head另一个保持不动然后两个指针都改成每次走一步当它们再次相遇时相遇点就是环的入口。4.1 推导过程为什么同速走一段就能锁定入口沿用上一节的符号X 是 head 到入口的距离Y 是入口沿前进方向到相遇点的距离L 是环长。我们已经得到 X Y mL所以 X mL - Y。设想现在有一辆新车从 head 出发每步走一个节点同时让原来在相遇点的指针也每步走一个节点。新车走了 X 步后到达入口旧指针从相遇点前进 X 步后它相对于入口的位置变化是 Y X。而 Y X m*L 正好是环长的整数倍也就是说旧指针转了整数圈之后也恰好落在入口。两车在入口汇合入口被锁定。很多资料会用相遇点到入口的距离恰好等于 head 到入口的距离来记忆更准确的说法其实是两者之间的差距是环长的整数倍而同速前进时这个整数圈差对在何处相遇没有任何影响。面试时我通常这样给面试官讲先确认相遇点然后派一个指针从头开始、一个指针从相遇点开始同速跑因为两个起点之间的弧长差是整圈所以它们必然在入口碰头。4.2 入口定位的完整代码def detect_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 相遇了说明存在环 slow head while slow is not fast: slow slow.next fast fast.next return slow return None注意这个写法把相遇判断和入口寻找合并到了一个循环里第一段循环条件不变一旦快慢指针相遇就跳出进入第二段同速追赶。如果链表无环第一段循环自然结束返回 None。代码很短但它集成了两个阶段理解每一步在做什么比背下来更重要。顺带一提入口定位有个很实用的自测价值你可以用它来验证 has_cycle 是否正确。我在本地测试时通常会构造一个入口在中间、环长比较大的链表先跑 detect_cycle 确认返回的节点确实在链表里再手动检查从这个节点继续走能否走回它自己。这种用 II 验证 I的做法比单独测布尔结果可靠得多。4.3 顺手算出环长既然已经能定位入口环长就是顺水推舟的事。最省事的办法是在找到入口后从入口开始重新绕一圈数回到入口一共经过多少节点。还有种更取巧的方式利用第一次相遇时快慢指针的步数关系反推环长但这样做容易混淆边界我一般只在讲原理时提一下工程实现里直接绕环计数最稳妥。def cycle_length(head): entry detect_cycle(head) if entry is None: return 0 length 1 cur entry.next while cur is not entry: cur cur.next length 1 return length这里从入口的下一个节点开始计数是为了避免一开始就把入口统计进去导致多算一个。这个细节同样容易出错建议自己动手跑一遍。5. 边界条件、常见错误与面试追问把细节扣到肌肉记忆代码能跑通简单用例不代表面试能过。环形链表这道题真正的区分度在于边界条件的处理和对算法正确性的解释是否自信。下面这些点是我在当面试官和被面试时都反复见过的。5.1 最容易翻车的三个边界首先空链表和单节点无环链表。head 为 null或 head.next 为 null此时直接返回 false。Floyd 算法的 while 条件fast and fast.next天然处理了这两种情况所以很少需要额外写 if。真正容易翻车的是只有一个节点且 next 指向自身的自环此时 fast 和 slow 都指向这个节点第一轮循环里 slow 走一步、fast 走两步实际上都是从自身出发回到自身然后slow is fast成立返回 true。建议你在写完代码后主动提示面试官测这个用例很多候选人都会在这里犹豫。其次环的入口正好在头节点也就是整个链表首尾相连。此时 X0相遇点一定在环内某个位置入口回推的第二步循环会让一个指针留在相遇点、另一个回到 head由于 head 就是入口slow 这一轮几乎没怎么移动就满足了条件直接返回 head。逻辑依然成立但如果你对推导不够熟面试时遇到这种输入容易怀疑自己写错了。第三环特别大、入口特别靠后。比如一万个节点入口在第 9997 个节点环长三千。这种用例能暴露 while 条件里fast and fast.next的判空顺序问题。只要 fast 在进入环前的最后一跳时 next 不为空就不会有空指针但如果你先判 fast.next 再判 fast当 fast 恰好停在倒数第二个节点时就会异常。所以顺序不要写反这也算是这道题里唯一一个跟语法习惯强相关的坑。5.2 面试官可能追问的几个问题为什么快指针走两步不能走三步吗这是最常见的追问。标准回答是走三步在有环的前提下未必会出错但正确性证明不如两步来得干净。走两步时fast 相对 slow 的速度是 1追及过程没有跳变走三步时相对速度是 2当环长为偶数、两者初始距离为奇数时可能出现一层层相邻错过的情况分析复杂度时徒增麻烦。所以面试时你只需要说两步保证相对速度为 1追及一定发生整体线性即可不必主动展开太深。如果链表很长fast 会不会提前走到 None这恰好说明无环直接返回 false。无环情况下链表是有限直线fast 每次跳跃两格必然更早到达终点。这是快慢指针方案里最直观的部分。哈希表和快慢指针你会选哪个我的标准答案是如果空间不是瓶颈、代码可维护性优先哈希表更不容易写错如果链表规模大、内存敏感或者节点本身不支持哈希快慢指针就是不二之选。面试时主动给出这种权衡对比比只报一个答案要加分。5.3 从面试题到工程直觉这个算法的用处不止于刷题最后说点题外话。这个算法在工程里的变体不少有些系统用类似的思路检测并发数据结构里的环路有些运行时工具用它分析对象引用是否存在循环还有配置解析器处理依赖关系时用它避免无限引用。工程版本通常不会写成链表 next 指针这么直白而是抽象成从任意状态按某种转移规则能否访问到已访问过的状态。我自己在实际项目里就遇到过类似的事一个配置文件解析器读取依赖关系列表依赖项之间允许互相引用。起初没做环检测结果某些异常的配置会让解析器陷入死循环表现为进程 CPU 占用打满。后来我用快慢指针的思路在依赖关系游走时快速判定环的存在几百个节点的配置规模下跑得飞快比维护一张全局访问哈希表省了不少内存。这大概就是刷题最实在的回报——你背下来的不是一道题的答案而是一种可以在完全不同的数据结构上迁移的思维模式。环形链表 I 值得好好吃透它真的不只是一道题。