说实话刷过“力扣hot100”这份清单的人多半绕不开第25题这道环形链表。它的题干很短给你链表的头节点 head判断链表中是否有环。可就是这个短题目藏了不少东西。第一次接触的人会脱口而出“用哈希表记录节点”但紧接着面试官会追问一句“能不能只用 O(1) 的空间?”这时候快慢指针这个经典解法才真正闪光。我今天想聊的不只是把代码贴出来让读者“膜拜一下”而是把这题背后的设计思路、边界条件、数学原理以及我实际调试时踩过的坑一次性说透。不管你是在准备面试、日常写业务代码还是做组件开发环形结构这套检测逻辑用到的场景远远比你想的要多。1. 先拆题环形链表的题目到底在问什么很多人第一次看这个题会觉得“环”是个很抽象的概念。我用一个生活化的场景来说明环形公交线路。站台之间是一条单向的环形路你从任意一个站上车走多久都到不了终点因为你始终在站与站之间循环。链表里的“环”也是这样——理论上单向链表的最后一个节点next 应该指向 null表示“到此结束”。但如果某个节点的 next 不是 null而是指向了链表中一个已经出现过的节点遍历就会陷入死循环。这个状态就是“有环”。题目核心其实就一句话判断遍历会不会无限进行下去能不能提前发现。它考核的是你对链表指针模型的熟悉程度而不是链表数值计算。1.1 输入输出与边界条件先对齐链表节点的定义在力扣环境里一般长这样class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }这里有一个非常关键的点判断环比较的是节点对象的地址也就是引用而不是节点里的 val。很多人在写哈希表方案时下意识地用 HashSet 去存节点值这是典型的错误。链表中值重复太常见了比如两个不同节点都是 2其中一个有环另一个没环你用值判断就会得到错误结论。正确做法是把整个 ListNode 对象存进去比如 HashSet 因为对象引用天然具备唯一性。边界条件通常包括head 为 null直接返回 false因为空链表不可能有环。只有一个节点且 next 指向 null返回 false。只有一个节点且 next 指向自己返回 true这是自环。多个节点环可能在中间也可能在末尾环的长度可能很长也可能很短。这些边界看起来简单却是很多人在现场写代码时最容易漏的地方。尤其自环这种形式如果实现不严谨循环一开始就可能陷入死循环代码根本跑不出来。1.2 这道题更深处考的是空间意识哈希表方案简单直白很多新手两分钟就能写出来。但它有个硬伤额外空间是 O(n)。如果链表长度达到百万级你就得为每个节点分配一个集合元素内存压力很大。面试官追问“能不能只用 O(1) 空间”其实是在考察你有没有建立空间复杂度的敏感度。环形链表的场景里需要破坏性修改节点吗不需要。所以不能用标记节点、修改 next 地址这类“脏”办法。既能不破坏原始数据又只需要常数级额外空间这才是快慢指针方案值得掌握的根本原因。2. 哈希表方案为什么它是面试官的首个预期如果你是第一次接触这道题哈希表是最自然的思路。遍历链表每到达一个节点就检查它是否已经出现过。如果出现过说明你从某个位置绕回来了那就证明有环如果一直走到 null 都没有重复节点那就说明链表是直线的。这种思路的本质是“记录历史”。用哈希集合把见过的节点记下来再拿新节点和历史记录比对。2.1 哈希表实现的完整代码import java.util.HashSet; import java.util.Set; public boolean hasCycle(ListNode head) { // 用 HashSet 保存已经遍历过的节点引用 SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { // 如果当前节点已经在集合中说明回到了之前走过的位置 if (seen.contains(cur)) { return true; } seen.add(cur); cur cur.next; } return false; }这段代码逻辑上没有任何问题。只要链表有环遍历就一定会在某个时刻回到重复节点。如果没有环循环会在 cur null 时自然终止。这里要注意的是“先检查后添加”的顺序。如果先 add 再 contains那么第一次遇到某个节点时也会报有环那就错乱了。2.2 复杂度分析与实际限制时间复杂度是 O(n)每个节点至多被访问一次哈希集合的查找和插入平均也是 O(1)。空间复杂度是 O(n)集合中最多保存 n 个节点的引用。对于十几万节点的链表这通常不是事但在资源受限的场景里你可能会发现内存占用超出了预期。另外哈希函数对对象引用计算 hashCode 时如果你的 ListNode 类重写了 hashCode 和 equals而且写得不合理可能引发额外的问题。力扣默认环境没这类坑但如果你自己写的业务类里重写了 equals再去当 HashSet 元素一定要确认“引用相等”的语义是否被破坏了。2.3 哈希表方案更大的价值提供正确性参照哈希表方案虽然空间不好但它逻辑简单非常适合当作“基准答案”来验证另一种解法的正确性。我在实际开发中经常这样做先用哈希表方案写一个验证版再换成快慢指针用随机生成的链表做对比测试。如果两个方法在所有用例下结果一致那基本可以确认快慢指针实现没有低级错误。所以我不建议直接跳过哈希表直奔快慢指针。能把两种方案讲清楚并且能说明各自的取舍才是面试里想要的完整回答。3. 快慢指针方案为什么两个速度不同的指针一定能相遇快慢指针又叫 Floyd 判圈算法也叫“龟兔赛跑”。思路不复杂设置两个指针慢指针 slow 每轮走一步快指针 fast 每轮走两步从同一个起点同时出发。如果链表没有环快指针会先到达 null如果链表有环那么快指针不会撞到 null而是会一直在环里转圈。由于快指针比慢指针快一步它最终会从后面追上慢指针。这里有个关键直觉两个人在同一个环形跑道上跑步一个速度快一个速度慢只要时间足够速度快的必然再次碰到速度慢的。我说的“再次”是因为一开始两人是同时同地出发的所以“第一次再相遇”一定发生在环内。3.1 快慢指针的完整实现public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }这段代码有几个细节值得仔细看。第一初始时 slow 和 fast 都指向 head。进入循环后先移动、再判断而不是先判断、再移动。如果你上来就写if (slow fast) return true;那么第一次判断时 slow 和 fast 都等于 head必然相等链表没环也会被误判成有环。第二循环条件必须是fast ! null fast.next ! null。因为 fast 每次跳两步只有确认 fast 当前不为 null且 fast 的下一个节点也不为 null才能安全执行fast.next.next。否则在链表的最后一个节点处fast.next 为 null再往下访问fast.next.next就会抛出空指针异常。第三返回值应该是“相遇”而不是“快指针走到 null”。很多初学者把逻辑反过来写快指针一走到 null 就返回 true把存在环的理解搞反了。没环时本来就该返回 false只有相遇才代表有环。3.2 数学证明为什么不会无限循环且一定能相遇我用最直白的话来证明这件事。假设链表存在一个环环的长度记为 L。慢指针 slow 从链表头部开始走它要走完入口之前的直线段然后进入环。设想 slow 刚到环入口的那一刻环入口节点记为 E。此时fast 因为速度是两步早就已经进入环了很可能已经在环里绕了若干圈。设 fast 当前距离入口节点 E 顺时针方向还有 p 步这个 p 一定在 0 到 L-1 之间。slow 和 fast 都进入环后每一轮更迭slow 往前走 1 步fast 往前走 2 步所以它们的相对距离每轮缩短 1 步。无论 fast 在环里的哪个位置它最终都会赶上 slow。最坏情况下fast 刚好就在 slow 前方一步那么下一轮就会相遇如果 fast 距离 slow 很远最多绕不到一整圈也会相遇。因此相遇一定发生而且发生在有限步内。时间复杂度也可以估算一下直线段长度 a环长度 L。slow 走到入口需要 a 步之后追上或被抓到最多需要 O(L) 步所以整体时间复杂度是 O(a L)等价于 O(n)。空间复杂度是 O(1)因为只使用了两个额外指针引用。3.3 快指针的速度为什么定成 2 而不是 3 或其他值这是一个经常被追问的问题。2 和 1 的组合足够好因为相对速度是 1。每一次循环快指针比慢指针多走一步追及过程非常平滑不会出现“跳过”的情况。如果快指针速度是 3慢指针是 1相对速度是 2。如果两者进入环时距离是奇数有可能出现一种情况快指针明明已经到了慢指针的位置但因为步幅跨过去了导致它们在下一轮才碰面。虽然这仍然不会造成死循环但分析起来麻烦也容易出错。面试沟通时选 2 和 1 不仅是性能最优也是数学模型最清晰的选择。这里补充一句快慢指针不仅能判断是否存在环还能在环存在的情况下继续定位环的入口和计算环的长度。这就是很多扩展题的来源也说明这道题并不是孤立的知识点。4. 从判断延伸到计算环的入口和环的长度怎么做面试官在问完“是否存在环”之后经常顺势加问一句“如果存在环能不能找到环的入口节点?”这就是力扣里另一道高频题。你如果能现场推导出来说明你不是背代码而是真的理解了环的数学结构。4.1 两步法定位环入口假设你已经通过快慢指针找到快慢指针的相遇点 M。现在做两件事从链表头部 head 出发用一个新指针 p1每轮走一步。从相遇点 M 出发用另一个指针 p2每轮走一步。当两者相遇时这个位置就是环的入口节点。听起来像魔法其实可以用距离等式解释。用 a 表示链表头到环入口的距离用 b 表示环入口沿着环方向到相遇点的距离用 L 表示环长。慢指针走的总距离是 a b。快指针走的总距离是 a b kL因为它比慢指针多走了 k 圈。由于快指针速度是慢指针的两倍所以有a b kL 2(a b)整理得到a kL - b这里 kL - b 的含义是“从相遇点继续走绕过若干圈后回到环入口所需的距离”。也就是说从相遇点出发走 a 步之后正好走到环入口。而从头部出发走 a 步也正好走到环入口。两者步速相同所以它们会在入口处相遇。代码实现public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; boolean hasCycle false; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) { return null; } ListNode p1 head; ListNode p2 slow; while (p1 ! p2) { p1 p1.next; p2 p2.next; } return p1; }这个经典解法经常让我觉得算法题的价值不只在于“通过测试用例”更在于你能否从速度和距离的关系里推出一个优雅的数学结论。4.2 计算环的长度计算环的长度可以复用相遇点。从任意一次相遇点开始保持指针不动用另一个临时指针环绕一圈数回这个相遇点走过的步数就是环长。具体代码int cycleLength(ListNode meetNode) { if (meetNode null) { return 0; } ListNode p meetNode.next; int len 1; while (p ! meetNode) { p p.next; len; } return len; }这里有个小陷阱如果 meetNode 为 null或者调用时链表其实没有环这个函数会死循环。所以在调用前必须先确认存在环并且 meetNode 是真实相遇点。工程上防御性编程意识体现在这种不起眼的调用前置条件上。4.3 从一道题到一类题变体与常见延伸环形链表这道题延伸出的变体很多很多面试官喜欢组合提问判断是否有环要求常量空间。找到环入口位置。计算环的长度。计算链表的总节点数或入口前的节点数。把环链表改写成无环链表即“断开环”。我在带团队时经常用这几个变体筛人。因为“是否有环”只要背模板就能过但“找入口”需要真正理解追及模型。理解了追及模型后面几个变体基本就是同一条思路的不同角度。5. 实际调试经验我踩过的坑和常用的排查方法在力扣上提交代码过了就算完成。但这类过程在真实工程里其实有非常多的细节坑。我把反复遇到过的几个问题整理在这里。5.1 死循环与空指针的先后顺序快慢指针最常见的问题就是判断条件写错。有人写成while (fast ! null) { slow slow.next; fast fast.next.next; ... }这种写法的别扭之处在于如果 fast 走到最后一个节点fast 不为 null但 fast.next 是 null执行 fast.next.next 时会直接空指针异常。你必须严格使用fast ! null fast.next ! null。另一个方向是循环条件里没有检查 fast 本身只检查 slow但 fast 速度更快先到达 null如果不检查 fast代码同样会在访问 fast.next 时崩溃。所以这个条件必须两个一起检查顺序也不能颠倒。Java 里的有短路求值先判断fast ! null再判断fast.next ! null是最安全的。5.2 单节点自环的测试判断只有一个节点且 next 指向自己的情况时很多人用哈希表方案不会出错但快慢指针方案如果初始就判断head null或者head.next null并直接返回 false就会误判自环。自环的定义是唯一的节点绕回自己它整体就是一个长度为一的环。如果你写出if (head null || head.next null) { return false; }那么自环会被拦在这个判断之外。所以更严谨的写法是把“出口”交给 while 循环去判断而不是在开头武断地过滤掉单节点。不过力扣上的标准测试用例里自环通常也是允许出现的最好直接用循环条件控制不要过早返回。5.3 使用 还是 equals 比较节点我在一些自测代码中发现有人用slow.equals(fast)或slow.val fast.val来判断相遇。前者的问题在于ListNode 默认的 equals 实际上就是比较地址除非你重写了 equals而如果你没重写 equals用 equals 和用 没有区别但显得不专业。后者的问题更大因为值相等不代表是同一个节点。记住一点环形链表里的“重复”是指同一个节点对象不是相同数值。所有指针比较都应该基于引用地址也就是直接使用slow fast。这不仅写起来简洁语义也更准确。5.4 手动构造测试用例的模板为了排查代码是否正确我经常手动构造几个特定形态的链表。这里顺便分享一个构造自环和中间环的方法// 自环一个节点指向自己 ListNode single new ListNode(1); single.next single; // 中间环1 - 2 - 3 - 4 - 2 ListNode n1 new ListNode(1); ListNode n2 new ListNode(2); ListNode n3 new ListNode(3); ListNode n4 new ListNode(4); n1.next n2; n2.next n3; n3.next n4; n4.next n2;把这两个用例分别塞进检测函数一个应该返回 true另一个也应该返回 true。再看无环用例ListNode a1 new ListNode(1); ListNode a2 new ListNode(2); a1.next a2; a2.next null;应该返回 false。这样就把边界情况覆盖了大半。5.5 调试时的“打印节点值”陷阱新手调试时喜欢打印 val。但对于有环的链表打印会永远停不下来。如果非要打印辅助信息建议打印节点对象的内存地址或者节点序号并且限制最大打印次数比如只打印前 20 个节点就退出。这样既能观察遍历路径又不会把终端刷爆。我的习惯是给每一步移动都加一个计数器超过某个阈值就主动停止并输出当前 slow 和 fast 的 val。这样即使链表有环也能快速发现是进入了死循环还是判断条件有问题。6. 工程场景里的环形检测不只是面试题很多人觉得这种题“面试用得上、工作用不上”。其实不然环形结构在真实系统里非常普遍只是它不以链表的样子出现。6.1 序列化与反序列化中的循环引用你写过一个包含父子引用的对象图吗比如一个员工对象里有 manager 字段manager 对象里又直接或间接包含这个员工对象。如果直接用 JSON 序列化库去做序列化库内部如果没有循环检测就会一直递归下去直到栈溢出。常见的 JSON 库在序列化时会对对象引用做标记一旦发现某个对象已经在序列化路径上就会抛异常或者自动截断。这种设计本质上就是“哈希集合 递归路径检查”的组合。你掌握了环形链表的哈希表方案就很容易理解为什么序列化库需要维护一个“正在处理的对象集合”。6.2 环形依赖与任务调度在构建工具、包管理器和模块加载器里模块之间的依赖关系如果用图表示一旦出现环就会形成“A 依赖 BB 又依赖 A”的死结。任务调度器需要检测这种环否则任务会永远等待。检测依赖环的算法可能不是简单的链表快慢指针但核心思想仍然是“遍历过程中发现重复节点”。6.3 内存回收与对象可达性分析垃圾回收器在标记可达对象时也要处理对象之间的循环引用。引用计数法处理不了循环引用但追踪式回收器会维护一个全局的“已访问对象集合”。这本质上又是哈希集合的变种应用。所以这道题看起来只是在讲链表实际上它让你掌握的能力可以迁移到很多地方识别循环、控制无限遍历、在 O(1) 空间里判断状态重复。这些能力在写中间件、基础组件和数据处理框架时特别重要。7. 我的实际体会怎么把这道题的价值榨干最后分享一点个人经验。如果你只是为了“刷过”看完答案背下来过两天大概率就忘了。我自己总结了一套比较高效的学习方法针对这种经典题尤其管用。先不看答案自己用哈希表写一遍确认正确性。然后逼迫自己在一小时内想出 O(1) 空间的方案。想不出来就去看快慢指针的代码但看完后合上答案自己再默写一遍。默写的时候看着那几个边界条件想想为什么每一条都要写。最后再把“找环入口”的变体推导一遍确保不是只会背。这样折腾完一道题比盲目刷十道题的效果都要好。这道环形链表更特殊因为它的证明并不复杂完全值得自己推导一次。我在实际工作中用过快慢指针检查一个处理日志的解析器状态机。日志流里偶尔会出现循环回溯导致解析进程长时间不退出。当时我不想给驻留进程增加额外内存记录就写了一个类似快慢指针的检测器定期把状态推进一下发现循环立刻报警。那个方案结构简单耗时也低算是我对这个算法印象最深的一次实际应用。力扣 Hot 100 里的题有价值的往往就是这种“题目短、考得深、延展多”的题。环形链表表面上是在问链表实际上是在考验你对指针模型、空间复杂度和循环结构的综合理解。把这道题吃透你再去碰其他链表题或者图相关的题目思路会顺畅很多。 
长河君 · 2026/10/20 4:31:12 · 阅读 1.2k 环形链表经典解法详解：快慢指针原理与工程应用
说实话刷过“力扣hot100”这份清单的人多半绕不开第25题这道环形链表。它的题干很短给你链表的头节点 head判断链表中是否有环。可就是这个短题目藏了不少东西。第一次接触的人会脱口而出“用哈希表记录节点”但紧接着面试官会追问一句“能不能只用 O(1) 的空间?”这时候快慢指针这个经典解法才真正闪光。我今天想聊的不只是把代码贴出来让读者“膜拜一下”而是把这题背后的设计思路、边界条件、数学原理以及我实际调试时踩过的坑一次性说透。不管你是在准备面试、日常写业务代码还是做组件开发环形结构这套检测逻辑用到的场景远远比你想的要多。1. 先拆题环形链表的题目到底在问什么很多人第一次看这个题会觉得“环”是个很抽象的概念。我用一个生活化的场景来说明环形公交线路。站台之间是一条单向的环形路你从任意一个站上车走多久都到不了终点因为你始终在站与站之间循环。链表里的“环”也是这样——理论上单向链表的最后一个节点next 应该指向 null表示“到此结束”。但如果某个节点的 next 不是 null而是指向了链表中一个已经出现过的节点遍历就会陷入死循环。这个状态就是“有环”。题目核心其实就一句话判断遍历会不会无限进行下去能不能提前发现。它考核的是你对链表指针模型的熟悉程度而不是链表数值计算。1.1 输入输出与边界条件先对齐链表节点的定义在力扣环境里一般长这样class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }这里有一个非常关键的点判断环比较的是节点对象的地址也就是引用而不是节点里的 val。很多人在写哈希表方案时下意识地用 HashSet 去存节点值这是典型的错误。链表中值重复太常见了比如两个不同节点都是 2其中一个有环另一个没环你用值判断就会得到错误结论。正确做法是把整个 ListNode 对象存进去比如 HashSet 因为对象引用天然具备唯一性。边界条件通常包括head 为 null直接返回 false因为空链表不可能有环。只有一个节点且 next 指向 null返回 false。只有一个节点且 next 指向自己返回 true这是自环。多个节点环可能在中间也可能在末尾环的长度可能很长也可能很短。这些边界看起来简单却是很多人在现场写代码时最容易漏的地方。尤其自环这种形式如果实现不严谨循环一开始就可能陷入死循环代码根本跑不出来。1.2 这道题更深处考的是空间意识哈希表方案简单直白很多新手两分钟就能写出来。但它有个硬伤额外空间是 O(n)。如果链表长度达到百万级你就得为每个节点分配一个集合元素内存压力很大。面试官追问“能不能只用 O(1) 空间”其实是在考察你有没有建立空间复杂度的敏感度。环形链表的场景里需要破坏性修改节点吗不需要。所以不能用标记节点、修改 next 地址这类“脏”办法。既能不破坏原始数据又只需要常数级额外空间这才是快慢指针方案值得掌握的根本原因。2. 哈希表方案为什么它是面试官的首个预期如果你是第一次接触这道题哈希表是最自然的思路。遍历链表每到达一个节点就检查它是否已经出现过。如果出现过说明你从某个位置绕回来了那就证明有环如果一直走到 null 都没有重复节点那就说明链表是直线的。这种思路的本质是“记录历史”。用哈希集合把见过的节点记下来再拿新节点和历史记录比对。2.1 哈希表实现的完整代码import java.util.HashSet; import java.util.Set; public boolean hasCycle(ListNode head) { // 用 HashSet 保存已经遍历过的节点引用 SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { // 如果当前节点已经在集合中说明回到了之前走过的位置 if (seen.contains(cur)) { return true; } seen.add(cur); cur cur.next; } return false; }这段代码逻辑上没有任何问题。只要链表有环遍历就一定会在某个时刻回到重复节点。如果没有环循环会在 cur null 时自然终止。这里要注意的是“先检查后添加”的顺序。如果先 add 再 contains那么第一次遇到某个节点时也会报有环那就错乱了。2.2 复杂度分析与实际限制时间复杂度是 O(n)每个节点至多被访问一次哈希集合的查找和插入平均也是 O(1)。空间复杂度是 O(n)集合中最多保存 n 个节点的引用。对于十几万节点的链表这通常不是事但在资源受限的场景里你可能会发现内存占用超出了预期。另外哈希函数对对象引用计算 hashCode 时如果你的 ListNode 类重写了 hashCode 和 equals而且写得不合理可能引发额外的问题。力扣默认环境没这类坑但如果你自己写的业务类里重写了 equals再去当 HashSet 元素一定要确认“引用相等”的语义是否被破坏了。2.3 哈希表方案更大的价值提供正确性参照哈希表方案虽然空间不好但它逻辑简单非常适合当作“基准答案”来验证另一种解法的正确性。我在实际开发中经常这样做先用哈希表方案写一个验证版再换成快慢指针用随机生成的链表做对比测试。如果两个方法在所有用例下结果一致那基本可以确认快慢指针实现没有低级错误。所以我不建议直接跳过哈希表直奔快慢指针。能把两种方案讲清楚并且能说明各自的取舍才是面试里想要的完整回答。3. 快慢指针方案为什么两个速度不同的指针一定能相遇快慢指针又叫 Floyd 判圈算法也叫“龟兔赛跑”。思路不复杂设置两个指针慢指针 slow 每轮走一步快指针 fast 每轮走两步从同一个起点同时出发。如果链表没有环快指针会先到达 null如果链表有环那么快指针不会撞到 null而是会一直在环里转圈。由于快指针比慢指针快一步它最终会从后面追上慢指针。这里有个关键直觉两个人在同一个环形跑道上跑步一个速度快一个速度慢只要时间足够速度快的必然再次碰到速度慢的。我说的“再次”是因为一开始两人是同时同地出发的所以“第一次再相遇”一定发生在环内。3.1 快慢指针的完整实现public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }这段代码有几个细节值得仔细看。第一初始时 slow 和 fast 都指向 head。进入循环后先移动、再判断而不是先判断、再移动。如果你上来就写if (slow fast) return true;那么第一次判断时 slow 和 fast 都等于 head必然相等链表没环也会被误判成有环。第二循环条件必须是fast ! null fast.next ! null。因为 fast 每次跳两步只有确认 fast 当前不为 null且 fast 的下一个节点也不为 null才能安全执行fast.next.next。否则在链表的最后一个节点处fast.next 为 null再往下访问fast.next.next就会抛出空指针异常。第三返回值应该是“相遇”而不是“快指针走到 null”。很多初学者把逻辑反过来写快指针一走到 null 就返回 true把存在环的理解搞反了。没环时本来就该返回 false只有相遇才代表有环。3.2 数学证明为什么不会无限循环且一定能相遇我用最直白的话来证明这件事。假设链表存在一个环环的长度记为 L。慢指针 slow 从链表头部开始走它要走完入口之前的直线段然后进入环。设想 slow 刚到环入口的那一刻环入口节点记为 E。此时fast 因为速度是两步早就已经进入环了很可能已经在环里绕了若干圈。设 fast 当前距离入口节点 E 顺时针方向还有 p 步这个 p 一定在 0 到 L-1 之间。slow 和 fast 都进入环后每一轮更迭slow 往前走 1 步fast 往前走 2 步所以它们的相对距离每轮缩短 1 步。无论 fast 在环里的哪个位置它最终都会赶上 slow。最坏情况下fast 刚好就在 slow 前方一步那么下一轮就会相遇如果 fast 距离 slow 很远最多绕不到一整圈也会相遇。因此相遇一定发生而且发生在有限步内。时间复杂度也可以估算一下直线段长度 a环长度 L。slow 走到入口需要 a 步之后追上或被抓到最多需要 O(L) 步所以整体时间复杂度是 O(a L)等价于 O(n)。空间复杂度是 O(1)因为只使用了两个额外指针引用。3.3 快指针的速度为什么定成 2 而不是 3 或其他值这是一个经常被追问的问题。2 和 1 的组合足够好因为相对速度是 1。每一次循环快指针比慢指针多走一步追及过程非常平滑不会出现“跳过”的情况。如果快指针速度是 3慢指针是 1相对速度是 2。如果两者进入环时距离是奇数有可能出现一种情况快指针明明已经到了慢指针的位置但因为步幅跨过去了导致它们在下一轮才碰面。虽然这仍然不会造成死循环但分析起来麻烦也容易出错。面试沟通时选 2 和 1 不仅是性能最优也是数学模型最清晰的选择。这里补充一句快慢指针不仅能判断是否存在环还能在环存在的情况下继续定位环的入口和计算环的长度。这就是很多扩展题的来源也说明这道题并不是孤立的知识点。4. 从判断延伸到计算环的入口和环的长度怎么做面试官在问完“是否存在环”之后经常顺势加问一句“如果存在环能不能找到环的入口节点?”这就是力扣里另一道高频题。你如果能现场推导出来说明你不是背代码而是真的理解了环的数学结构。4.1 两步法定位环入口假设你已经通过快慢指针找到快慢指针的相遇点 M。现在做两件事从链表头部 head 出发用一个新指针 p1每轮走一步。从相遇点 M 出发用另一个指针 p2每轮走一步。当两者相遇时这个位置就是环的入口节点。听起来像魔法其实可以用距离等式解释。用 a 表示链表头到环入口的距离用 b 表示环入口沿着环方向到相遇点的距离用 L 表示环长。慢指针走的总距离是 a b。快指针走的总距离是 a b kL因为它比慢指针多走了 k 圈。由于快指针速度是慢指针的两倍所以有a b kL 2(a b)整理得到a kL - b这里 kL - b 的含义是“从相遇点继续走绕过若干圈后回到环入口所需的距离”。也就是说从相遇点出发走 a 步之后正好走到环入口。而从头部出发走 a 步也正好走到环入口。两者步速相同所以它们会在入口处相遇。代码实现public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; boolean hasCycle false; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) { return null; } ListNode p1 head; ListNode p2 slow; while (p1 ! p2) { p1 p1.next; p2 p2.next; } return p1; }这个经典解法经常让我觉得算法题的价值不只在于“通过测试用例”更在于你能否从速度和距离的关系里推出一个优雅的数学结论。4.2 计算环的长度计算环的长度可以复用相遇点。从任意一次相遇点开始保持指针不动用另一个临时指针环绕一圈数回这个相遇点走过的步数就是环长。具体代码int cycleLength(ListNode meetNode) { if (meetNode null) { return 0; } ListNode p meetNode.next; int len 1; while (p ! meetNode) { p p.next; len; } return len; }这里有个小陷阱如果 meetNode 为 null或者调用时链表其实没有环这个函数会死循环。所以在调用前必须先确认存在环并且 meetNode 是真实相遇点。工程上防御性编程意识体现在这种不起眼的调用前置条件上。4.3 从一道题到一类题变体与常见延伸环形链表这道题延伸出的变体很多很多面试官喜欢组合提问判断是否有环要求常量空间。找到环入口位置。计算环的长度。计算链表的总节点数或入口前的节点数。把环链表改写成无环链表即“断开环”。我在带团队时经常用这几个变体筛人。因为“是否有环”只要背模板就能过但“找入口”需要真正理解追及模型。理解了追及模型后面几个变体基本就是同一条思路的不同角度。5. 实际调试经验我踩过的坑和常用的排查方法在力扣上提交代码过了就算完成。但这类过程在真实工程里其实有非常多的细节坑。我把反复遇到过的几个问题整理在这里。5.1 死循环与空指针的先后顺序快慢指针最常见的问题就是判断条件写错。有人写成while (fast ! null) { slow slow.next; fast fast.next.next; ... }这种写法的别扭之处在于如果 fast 走到最后一个节点fast 不为 null但 fast.next 是 null执行 fast.next.next 时会直接空指针异常。你必须严格使用fast ! null fast.next ! null。另一个方向是循环条件里没有检查 fast 本身只检查 slow但 fast 速度更快先到达 null如果不检查 fast代码同样会在访问 fast.next 时崩溃。所以这个条件必须两个一起检查顺序也不能颠倒。Java 里的有短路求值先判断fast ! null再判断fast.next ! null是最安全的。5.2 单节点自环的测试判断只有一个节点且 next 指向自己的情况时很多人用哈希表方案不会出错但快慢指针方案如果初始就判断head null或者head.next null并直接返回 false就会误判自环。自环的定义是唯一的节点绕回自己它整体就是一个长度为一的环。如果你写出if (head null || head.next null) { return false; }那么自环会被拦在这个判断之外。所以更严谨的写法是把“出口”交给 while 循环去判断而不是在开头武断地过滤掉单节点。不过力扣上的标准测试用例里自环通常也是允许出现的最好直接用循环条件控制不要过早返回。5.3 使用 还是 equals 比较节点我在一些自测代码中发现有人用slow.equals(fast)或slow.val fast.val来判断相遇。前者的问题在于ListNode 默认的 equals 实际上就是比较地址除非你重写了 equals而如果你没重写 equals用 equals 和用 没有区别但显得不专业。后者的问题更大因为值相等不代表是同一个节点。记住一点环形链表里的“重复”是指同一个节点对象不是相同数值。所有指针比较都应该基于引用地址也就是直接使用slow fast。这不仅写起来简洁语义也更准确。5.4 手动构造测试用例的模板为了排查代码是否正确我经常手动构造几个特定形态的链表。这里顺便分享一个构造自环和中间环的方法// 自环一个节点指向自己 ListNode single new ListNode(1); single.next single; // 中间环1 - 2 - 3 - 4 - 2 ListNode n1 new ListNode(1); ListNode n2 new ListNode(2); ListNode n3 new ListNode(3); ListNode n4 new ListNode(4); n1.next n2; n2.next n3; n3.next n4; n4.next n2;把这两个用例分别塞进检测函数一个应该返回 true另一个也应该返回 true。再看无环用例ListNode a1 new ListNode(1); ListNode a2 new ListNode(2); a1.next a2; a2.next null;应该返回 false。这样就把边界情况覆盖了大半。5.5 调试时的“打印节点值”陷阱新手调试时喜欢打印 val。但对于有环的链表打印会永远停不下来。如果非要打印辅助信息建议打印节点对象的内存地址或者节点序号并且限制最大打印次数比如只打印前 20 个节点就退出。这样既能观察遍历路径又不会把终端刷爆。我的习惯是给每一步移动都加一个计数器超过某个阈值就主动停止并输出当前 slow 和 fast 的 val。这样即使链表有环也能快速发现是进入了死循环还是判断条件有问题。6. 工程场景里的环形检测不只是面试题很多人觉得这种题“面试用得上、工作用不上”。其实不然环形结构在真实系统里非常普遍只是它不以链表的样子出现。6.1 序列化与反序列化中的循环引用你写过一个包含父子引用的对象图吗比如一个员工对象里有 manager 字段manager 对象里又直接或间接包含这个员工对象。如果直接用 JSON 序列化库去做序列化库内部如果没有循环检测就会一直递归下去直到栈溢出。常见的 JSON 库在序列化时会对对象引用做标记一旦发现某个对象已经在序列化路径上就会抛异常或者自动截断。这种设计本质上就是“哈希集合 递归路径检查”的组合。你掌握了环形链表的哈希表方案就很容易理解为什么序列化库需要维护一个“正在处理的对象集合”。6.2 环形依赖与任务调度在构建工具、包管理器和模块加载器里模块之间的依赖关系如果用图表示一旦出现环就会形成“A 依赖 BB 又依赖 A”的死结。任务调度器需要检测这种环否则任务会永远等待。检测依赖环的算法可能不是简单的链表快慢指针但核心思想仍然是“遍历过程中发现重复节点”。6.3 内存回收与对象可达性分析垃圾回收器在标记可达对象时也要处理对象之间的循环引用。引用计数法处理不了循环引用但追踪式回收器会维护一个全局的“已访问对象集合”。这本质上又是哈希集合的变种应用。所以这道题看起来只是在讲链表实际上它让你掌握的能力可以迁移到很多地方识别循环、控制无限遍历、在 O(1) 空间里判断状态重复。这些能力在写中间件、基础组件和数据处理框架时特别重要。7. 我的实际体会怎么把这道题的价值榨干最后分享一点个人经验。如果你只是为了“刷过”看完答案背下来过两天大概率就忘了。我自己总结了一套比较高效的学习方法针对这种经典题尤其管用。先不看答案自己用哈希表写一遍确认正确性。然后逼迫自己在一小时内想出 O(1) 空间的方案。想不出来就去看快慢指针的代码但看完后合上答案自己再默写一遍。默写的时候看着那几个边界条件想想为什么每一条都要写。最后再把“找环入口”的变体推导一遍确保不是只会背。这样折腾完一道题比盲目刷十道题的效果都要好。这道环形链表更特殊因为它的证明并不复杂完全值得自己推导一次。我在实际工作中用过快慢指针检查一个处理日志的解析器状态机。日志流里偶尔会出现循环回溯导致解析进程长时间不退出。当时我不想给驻留进程增加额外内存记录就写了一个类似快慢指针的检测器定期把状态推进一下发现循环立刻报警。那个方案结构简单耗时也低算是我对这个算法印象最深的一次实际应用。力扣 Hot 100 里的题有价值的往往就是这种“题目短、考得深、延展多”的题。环形链表表面上是在问链表实际上是在考验你对指针模型、空间复杂度和循环结构的综合理解。把这道题吃透你再去碰其他链表题或者图相关的题目思路会顺畅很多。