环形链表检测：哈希表与快慢指针的工程取舍

上个月帮朋友排查一个线上问题某个服务跑着跑着 CPU 就飙到 100%日志停在数据导出任务上再也不动重启能恢复过几个小时又复现。把线程栈打出来才发现遍历逻辑卡在一个互相引用的对象图上代码里没有做访问标记指针永远走不到尽头。这类问题在链表这种结构上有个更基础、也更值得单独拎出来的版本判断一条链表是否是环形链表。说白了就是给你一个头节点你只允许顺着 next 往下走要判断这条链会不会绕回已经走过的节点。这个判断看起来简单写法却藏着不少坑空指针、单节点自环、快慢指针初始位置、循环条件顺序任何一个写错都会让程序在测试环境跑得好好的到了线上长链表上才炸。这篇文章面向三类人准备面试需要把两种解法讲清楚的写业务代码时需要给链表或对象图加一层防环校验的以及做底层数据结构维护、需要在 O(1) 额外空间下判断结构完整性的。我会把哈希表记录法和快慢指针法两种解法的判定依据、数学原理、代码实现、实测性能、踩坑记录全部摊开讲代码给到可以直接复现的程度。1. 先把问题说透环形链表到底长什么样1.1 从一次 CPU 打满的排查说起那次问题的现场很有意思。业务代码里有一个自制的缓存结构节点之间用 next 串起来正常逻辑下最后一个节点的 next 应该是 null。某次数据迁移脚本写错了一个分支把尾节点的 next 指回了中间的某个节点于是这条链从一个有限序列变成了一个带尾巴的环。遍历函数写的是最朴素的while (cur ! null)从那一刻起它就再也没停下来过每轮循环只做一次指针跳转和一次字段读取CPU 占用不高但一直占着接口线程池被慢慢耗干表现出来就是响应越来越慢直到完全卡死。这类问题的隐蔽之处在于它不会立刻报错也不会抛异常只是安静地转圈。如果是数组越界程序当场就崩了排查反而简单环形链表这种“逻辑上永远不结束”的故障往往要等到资源耗尽才暴露中间可能已经过去几个小时。所以工程上常见的做法是在所有遍历外部输入链表的地方先做一次环形检测代价是 O(n) 的时间换回来的是确定性。这笔账怎么算都划算尤其是跨服务传过来的数据结构你没法保证对方一定没写错。另外还有一类场景不是“故障”而是“正常业务”对象图序列化。一个对象可能被多个字段引用形成引用闭环序列化器如果不做已访问标记就会无限递归直到栈溢出。链表是对象图退化成单分支后的特例把链表上的环形判断想清楚了对象图上做访问标记的思路也就顺了。所以这个题看起来是面试题实际上是很多底层工具的地基。1.2 三种典型形态与判定目标环形链表不是只有一种长相实际写代码时得把这几种都想到否则测试用例覆盖不全很容易漏掉边界。第一种是尾部成环形如1 - 2 - 3 - 4 - 5 - 3前段是一条正常链尾节点指回了中间某个节点。第二种是整体成环像1 - 2 - 3 - 1从头节点开始就在环里没有任何“尾巴”。第三种是自环只有一个节点node.next node这种最容易被漏掉因为很多实现的初始判断直接把单节点当成了无环。还有一种极端情况是双节点互指1 - 2 - 1环长只有 2。这个形态专门用来打那些“快指针一次走两步”但初始位置写错的代码因为快指针走两步正好跳回自己如果实现里判断逻辑有偏差很容易在这里出现空指针或者直接判定错误。判定目标本身要说清楚我们要判断的是链表的拓扑结构里是否存在环而不是“是否存在重复的值”。这两件事必须分开。链表里出现两个值相同的节点太正常了1 - 2 - 1 - null里有两个 1但它不是环形链表。判定依据必须是节点的内存引用Java 里的对象引用、C/C 里的指针地址、Python 里的对象 id而不是 val 字段。这一点在后面讲哈希表法时会展开因为用错判据的实现实在太多了。1.3 两种解法背后的取舍逻辑目前主流就两条路。第一条是哈希表法遍历时把走过的每个节点引用塞进一个集合每走一步先查这个节点是不是已经在集合里如果在说明绕回来了判定为有环。逻辑极其直白正确性几乎不需要证明缺点是额外空间是 O(n)链表有多长就要存多少个节点引用。第二条是快慢指针法也叫龟兔赛跑法上世纪六十年代就有人提出并证明过。两个指针从头出发慢指针每次走一步快指针每次走两步。如果链表无环快指针会先走到 null循环自然结束如果有环快指针会先进环然后在一个有限的步数内追上慢指针。空间复杂度 O(1)时间复杂度 O(n)是这道题的标准答案。取舍的关键在于约束条件。如果你在写业务代码手头有足够内存追求的是最快落地和最少出错哈希表法更稳妥因为它的正确性对初始位置、步长、循环条件都不敏感。如果你在做嵌入式、驱动、或者需要处理百万级节点且内存紧张的场景快慢指针是唯一选择因为哈希表法在这种规模下真的会把内存吃掉一大块我在第 4 节会给出实测的量级数据。还有一种情况是链表节点不允许被修改成“已访问”标记这时候标记法把访问过的节点 val 改成一个哨兵值也不能用只剩快慢指针这一条路。2. 哈希表法用空间换确定性的兜底方案2.1 判定依据为什么是“节点引用”而不是“节点值”先把最容易踩的坑摆在前面。我见过不止一份代码把节点值当成了 key 塞进 Set写成set.add(cur.val)然后判断if (!set.add(cur.val)) return true;。这段代码在线表里没有重复值的时候看起来一切正常一旦链表里出现两个值相同的不同节点立刻误判成环。比如1 - 2 - 1 - null走到第三个节点时 val 是 1集合里已经有 1 了直接返回“有环”但这条链明明是有限的。正确的判据是节点对象本身。Java 里HashSetNode存的是引用两个不同节点即使 val 相同只要没有重写 equals 和 hashCode默认就是按对象身份比较的add返回 false 只可能因为同一个对象被加了第二次。Python 里set存对象也是按__hash__和__eq__走的默认实现基于对象 id同样符合预期。C 里存指针地址语义更直接。所以只要节点类老老实实没重写相等性方法用引用做 key 就是对的。这里有个实操技巧值得记一下Java 的Set.add()有返回值返回 false 表示元素已存在可以直接把“判断 插入”合成一步少写一次contains调用。看着只省了一次哈希计算但在百万级节点的链表上这一次调用能省掉将近一半的时间。我实测过 100 万节点的无环链表分开写contains再add大概要 300 毫秒上下合并成一步能压到 180 毫秒左右。这个优化在业务代码里微不足道但在高频调用的工具方法里确实有效。2.2 Java 与 Python 的落地写法先给 Java 版本这是最常见的生产写法。节点定义保持最简只有 val 和 next 两个字段不重写任何方法这样默认的身份哈希正好符合我们的需求static class Node { int val; Node next; Node(int val) { this.val val; } } public static boolean hasCycleBySet(Node head) { SetNode visited new HashSet(); Node cur head; while (cur ! null) { if (!visited.add(cur)) { // add 返回 false 说明这个节点走过了 return true; } cur cur.next; } return false; }Python 版本稍微需要注意一点。Python 的set里放对象默认按id哈希、按is比较只要节点类没重写__eq__和__hash__直接存对象是没问题的。但如果节点用了 dataclass 的eqTrue情况就变了所以我更倾向于显式存id(cur)把“按身份判断”这个意图写死在代码里不依赖类的默认行为def has_cycle_by_set(head): seen set() cur head while cur is not None: key id(cur) # 显式用对象身份做 key避免 __eq__ 被重写后误判 if key in seen: return True seen.add(key) cur cur.next return False用id(cur)还有一个附带好处整型比对象引用更容易被哈希表优化集合内部的内存布局更紧凑同样一百万节点存 id 的集合内存占用大概是存对象的六成左右。当然这个差异在常规规模下可以忽略只是为了说明“显式表达意图”这件事本身有价值。2.3 重写 equals 带来的隐蔽坑这一条是真实踩过的。某开发者在做一个数据清洗工具节点类用了 Lombok 的Data注解等于自动生成了基于所有字段的 equals 和 hashCode。哈希表法在这份代码上跑起来的结果是只要链表里有两个 val 相同的节点就判定为有环。更麻烦的是这种 bug 很难在单测里被发现因为测试数据往往是递增的 1、2、3、4没有重复值全部通过上线遇到真实数据里带重复值的场景直接开始误报。解决办法有三个层次。最省事的是不改节点类改用身份哈希的集合Java 里可以写Collections.newSetFromMap(new IdentityHashMap())得到的集合完全按比较跟 equals 实现彻底解耦。第二个办法是手动包装一层存System.identityHashCode(cur)但要注意 hashCode 理论上可能碰撞碰撞后需要用再确认一次代码会变啰嗦。最彻底的办法是在工具方法里明确约定本方法要求节点类不重写 equals/hashCode在方法注释里写清楚谁改谁负责。同样的坑在 Python 里表现为dataclass(eqTrue)会生成__eq__并把__hash__置为 None导致对象直接不可哈希塞进 set 会抛TypeError: unhashable type。如果加了frozenTrue__hash__会被生成按字段计算哈希于是又回到误判那条路。所以 Python 侧用id()是最稳的写法不依赖任何类的默认行为。2.4 复杂度与适用边界时间复杂度 O(n)n 是链表节点数每个节点最多访问一次哈希表插入和查询均摊 O(1)。空间复杂度 O(n)最坏情况是无环链表所有节点都要存下来。这个 O(n) 的空间在很多场景下完全可接受比如几千个节点的配置链、几百个节点的路由表内存开销可以忽略不计。真正需要警惕的是规模。Java 的HashSet每个元素在底层是一个HashMap.Node包含 hash、key、next、value 四个字段加上对象头64 位 JVM 上大约 32 字节再算上底层数组的负载因子 0.75实际每个元素占用接近 43 字节。一百万节点的链表光集合本身就要 40 多 MB还没有算 Node 对象本身。在一个堆内存 512 MB 的容器里这种开销足以触发频繁 GC甚至 OOM。我在第 4 节会给出实测数据。适用边界可以总结成一句话节点规模在十万以内、内存不敏感、追求代码正确性优先的场景哈希表法是首选因为它几乎不会写错。超过这个规模或者代码跑在内存受限的环境里就该换快慢指针了。提示如果只是想在调试阶段快速确认一条链表有没有环哈希表法是更好的选择因为它天然能记录下“从哪个节点开始重复”配合一次打印就能定位环的入口排查效率比快慢指针高得多。3. 快慢指针法O(1) 空间的老牌解法3.1 追及逻辑为什么一定成立快慢指针的核心逻辑用一句话概括两个人在一条环形跑道上同向跑一个快一个慢快的那个迟早会从背后追上慢的。放在链表上慢指针每次走一步快指针每次走两步如果链表无环快指针会先撞到 null循环结束返回 false如果有环两个指针都会先后进入环内由于快指针速度更快它会在环内不断缩短与慢指针的距离最终两者指向同一个节点。这个“迟早追上”的直觉需要一个前提环是有限的、快慢速度差是固定的。只要满足这两点追及就必然发生。很多人第一次接触会疑惑快指针会不会正好“跳过”慢指针答案是在快指针每次走两步、慢指针每次走一步的设定下不会。原因是每轮循环两者在环上的相对位置只变化 1 个节点快指针相对慢指针是“一步一步逼近”的不存在跨过去的情况。这一点在下一节会用相对速度严格说明也是“为什么步长必须选 2”这个问题的答案。还有一点容易忽略慢指针进入环之前快指针可能已经在环里转了好几圈。这不影响结论因为一旦慢指针也进入环两者就处于同一条环形跑道上追及问题就退化成了两个匀速运动物体的追及问题跟快指针提前转了几圈无关。数学上多转的圈数会体现在方程里的那个整数倍环长上最终会抵消掉。3.2 用相对速度把“一定相遇”算清楚把慢指针的速度设为 1 个节点每步快指针设为 2 个节点每步那么在慢指针的参考系里快指针的相对速度是 1 个节点每步。也就是说慢指针进入环之后快指针相对于慢指针的距离每轮减少 1。环长是有限的设为 L那么最多经过 L - 1 轮相对距离就会减到 0两者指向同一个节点。换个角度看这是个模运算问题。设慢指针刚进入环时快指针在环上距离慢指针顺时针方向有 d 个节点0 ≤ d L。每轮循环后相对距离变成(d - 1) mod L。因为相对速度是 1与任何环长 L 都互质所以这个序列会遍历环上的所有位置d 必然会取到 0 这个值。这就是“一定能追上”的严格理由。反过来说只要两个指针都进了环追上是必然的时间上界是 L 步。再算上慢指针走到环入口之前走过的路径长度总的时间复杂度是 O(n)因为整个过程中快指针最多把链表走两遍左右不会有更差的情况。这个结论很关键快慢指针法不只是空间省它在时间上也是最坏 O(n)不存在某些人担心的“环很大导致超时”的问题。3.3 步长为什么锁定为 2 而不是 3这是个能区分“背过答案”和“真的想明白了”的问题。假设快指针每次走 k 步慢指针走 1 步相对速度就是 k - 1。沿用上一节的模运算模型相对距离的变化是(d - (k-1)) mod L。要让这个序列从任意初值 d 出发都能到达 0需要 k - 1 与 L 互质也就是gcd(k-1, L) 1。问题在于环长 L 在检测之前是未知的你无法保证某个固定的 k - 1 跟所有的 L 都互质。k 2 时k - 1 11 与任何正整数都互质所以无论环长是多少都必然相遇。这是唯一一个能对任意 L 都成立的步长选择。k 3 时k - 1 2。如果环长 L 是偶数那么gcd(2, L) 2相对距离序列只能在某个奇偶性固定的集合里变化。具体来说如果慢指针进环时相对距离 d 是奇数那么每轮减 2 再对 L 取模得到的永远是奇数永远取不到 0。结果就是快指针在环里一直转圈追不上循环变成死循环。这个错误在实践中真的会出现有人觉得“快指针走快点能更早追上”改成三步、四步测试用例用的是三节点环L 3跟 2 互质跑起来没问题线上遇到四节点环直接卡死。所以 k 2 不是随便选的它是唯一的安全解。至于为什么不再考虑 k 1.5 这种非整数速度那是因为链表的移动最小单位就是一个节点没法走半步。这个结论记住就行快慢指针的步长只有 1 和 2 这一对组合可以无条件使用。3.4 循环条件的书写顺序与边界代码实现上最标准的写法是这样public static boolean hasCycle(Node head) { Node slow head; Node fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }这段代码有三个细节必须注意。第一个是循环条件的顺序fast ! null fast.next ! null不能反写成fast.next ! null fast ! null。Java 的是短路的从左到右求值先判断 fast 非空才能安全地访问 fast.next。反过来写当 fast 为 null 时会直接抛空指针。第二个是fast.next.next的安全性。进入循环体的前提是fast ! null且fast.next ! null所以fast.next.next最多是 null不会抛异常赋值给 fast 之后下一轮循环条件会把它拦住。这个推理要能自己走一遍否则改代码的时候容易手抖。第三个是初始位置。上面这版 slow 和 fast 都从头节点出发循环体里先移动再比较所以自环节点node.next node的场景是第一轮 slow 和 fast 都指回自己比较相等返回 true正确。空链表head null时循环条件直接不满足返回 false也正确。有些写法把 fast 初始化为head.next先移动再进循环也能工作但要额外处理head null || head.next null的提前返回代码反而更长。我更推荐上面这版边界处理天然内聚在循环条件里。4. 动手实操把两种方法跑起来并做对比4.1 节点定义与造环工具要验证两种方法得先能造出各种形态的链表。核心是一个工具方法给定链表长度和环入口位置构造出一条带环的链环入口位置传 -1 表示无环。实现思路是先按长度把节点串起来再找到第 pos 个节点把尾节点的 next 指过去static Node buildList(int size, int cyclePos) { if (size 0) return null; Node[] nodes new Node[size]; for (int i 0; i size; i) { nodes[i] new Node(i); } for (int i 0; i size - 1; i) { nodes[i].next nodes[i 1]; } if (cyclePos 0 cyclePos size) { nodes[size - 1].next nodes[cyclePos]; // 尾节点指回指定位置 } return nodes[0]; }这段工具有个细节当size 1且cyclePos 0时nodes[0].next nodes[0]正好构造出自环。当cyclePos size - 1时尾节点指回自己也是自环。这两种情况都要能在测试里覆盖到。另外注意nodes数组只是构造阶段的辅助构造完成后链表本身不持有这个数组不会影响后续的内存测量。Python 版本思路一致用列表暂存节点引用即可注意最后一个节点的 next 赋值要放在循环外面否则会在构造阶段就形成环导致后续的串接逻辑失效。这个顺序问题我第一次写的时候就搞反了结果造出来的链表只有两个节点在互相指跟预期完全不符排查了半天。4.2 六组必测用例测试用例的设计比代码本身更重要因为快慢指针这类算法的 bug 几乎全在边界上。我整理了一张表这六组跑通基本可以认为实现是正确的用例编号构造方式期望结果考察点1head nullfalse空链表不抛异常2单节点next nullfalse单节点无环3单节点next 指向自己true自环4两节点互指1 - 2 - 1true最小环长快指针容易在这里出错51000 节点尾节点指向第 500 个true长尾环验证追及步数6100000 节点无环false长链表性能与不误判用例 4 特别值得单独说。环长 L 2快指针每次走两步正好在环内来回跳如果实现里循环条件写错、或者初始位置处理不当这里最容易暴露。用例 5 的环入口在中间慢指针要走 500 步才进环快指针早就进环转了不知道多少圈专门用来验证“快指针提前进环不影响结论”这个理论点。用例 6 则是反向验证无环的长链表必须返回 false而且要在合理时间内返回。我一般还会加一组随机测试随机生成长度 0 到 10000 的链表随机决定是否有环、环入口在哪跑一千次两种方法的结果必须完全一致。这种对拍测试能抓到很多手工用例想不到的组合尤其是那些只在特定长度和特定环入口下才出现的初始位置 bug。4.3 实测性能对比环境说明普通笔记本JVM 堆上限 2 GB节点为最简单的双字段对象每组数据跑十次取中位数。数据只给量级参考不同机器和不同 JVM 参数下会有差异但数量级关系是稳定的。节点规模是否有环哈希表法耗时快慢指针耗时哈希表额外内存1 万无环3 ms 左右小于 1 ms约 0.5 MB10 万无环30 ms 左右2 ms 左右约 5 MB100 万无环300 ms 左右20 ms 左右约 50 MB100 万尾环在第 50 万个180 ms 左右15 ms 左右约 25 MB500 万无环约 1.6 s100 ms 左右约 250 MB从数据能看出几件事。第一快慢指针在时间上普遍快一个数量级原因是哈希表法每次插入都要算哈希、定位桶、处理可能的扩容而快慢指针只是两次指针跳转指令数少得多。第二哈希表法的额外内存是实打实的一百万节点五十兆五百万节点两百多兆在容器内存受限的环境里这是能压垮服务的那根稻草。第三有环的情况下哈希表法耗时会减半因为它遍历到环入口走一圈就返回了而快慢指针的耗时基本不变它本来就要走到相遇点。还有一个不太直观的结论快慢指针的耗时对“有没有环”不敏感对“环入口在哪”也不敏感基本就是线性增长。这是因为快指针最多把链表走两遍总步数被 n 限制住了。而哈希表法的耗时在无环时是完整的 n 次插入有环时只插入到环入口为止所以环越靠前越快。这个特性在排查阶段有点用如果同一份数据跑两次耗时差异很大说明环的位置可能变了或者数据规模变了。4.4 顺带扩展找环入口与算环长判断有没有环只是第一层工程上经常还需要知道环从哪开始、环有多长。这两个问题都是快慢指针法天然的延伸哈希表法反而要额外遍历一次才能算出来。找环入口的推导值得完整走一遍。设头节点到环入口的距离为 a环入口到相遇点的距离为 b相遇点继续走到环入口的距离为 c那么环长 L b c。慢指针走过的路程是 a b快指针走过的路程是 a b kLk 是快指针在环里多转的圈数k ≥ 1。因为快指针速度是慢指针的两倍所以a b kL 2(a b) kL a b a kL - b (k - 1)L c这个式子的意思是从头节点走到环入口的距离 a等于从相遇点走到环入口的距离 c再加上整数圈。所以只要在相遇之后让一个指针从头节点出发另一个指针从相遇点出发两者每次都走一步它们一定会在环入口相遇。k 1 时就是 a c走的步数最少。public static Node detectCycle(Node head) { Node slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { Node p head; while (p ! slow) { // 一个从头走一个从相遇点走同速 p p.next; slow slow.next; } return p; } } return null; // 无环 }环长的计算更简单在相遇点固定一个指针另一个指针沿着 next 走一圈回到相遇点时计数值就是环长。注意这里不要用 do-while 写成先走再判断起始计数应该是 1 而不是 0否则会少算一个。这种差一错误在小环上特别明显比如环长 2 的情况数错一次结果就变成 1 了肉眼很难发现。5. 常见问题与排查实录5.1 空指针的三个高发位置快慢指针的空指针问题几乎全部来自循环条件和指针解引用。第一个高发点是循环条件顺序写反fast.next ! null fast ! null在 fast 为 null 时先访问了 fast.next直接 NPE。这个错误在 IDE 里不会有任何提示编译也能通过只有跑起来才炸而且要跑到链表尾部才会触发所以单节点测试往往发现不了。第二个高发点是漏判fast.next ! null。只写while (fast ! null)然后在循环体里直接fast fast.next.next。当 fast 落在最后一个节点上时fast.next 是 null再取 null.next 就抛异常了。这种写法在无环链表上必然出错在有环链表上反而可能正常因为 fast 永远走不到尾部。所以测试用例里一定要有无环的长链表。第三个高发点是初始移动。有些实现写成fast head.next; slow head;然后直接进 while 循环比较如果 head 本身是 nullhead.next当场就炸。正确的做法是在方法入口判断head null || head.next null直接返回或者干脆用 3.4 节那版统一从头出发的写法把边界条件交给循环条件处理。5.2 初始值导致的一步误判这个坑很隐蔽代码长这样Node slow head, fast head; while (slow ! fast) { // 错误初始就相等循环一次都不进 // ... }因为 slow 和 fast 都初始化成 headwhile 条件一开始就是 false循环体一次都不执行方法直接返回一个默认值。如果后面的逻辑写的是“循环结束后返回 true”那么任何链表都会被判定为有环包括空链表。这个 bug 在某些写法里会导致全量误报但因为返回的是 true 而不是抛异常测试如果不校验具体期望值很容易漏过去。修法有三种改成 do-while先移动再判断把比较挪到循环体内部循环条件只写 fast 的空判断或者初始化时让 fast 先走一步。我个人偏好第二种就是 3.4 节那版逻辑最清晰边界条件也最集中。第一种虽然代码短但 do-while 在 Java 里容易被误读团队协作时不如显式写法直观。顺带说一句慢指针的初始位置也有讲究。如果慢指针从head.next开始、快指针从 head 开始理论上也能工作但分析起来要分情况讨论容易出错。统一从头出发是最不容易出问题的选择。5.3 并发修改下的诡异现象这个不是算法本身的问题而是使用场景的问题。如果链表在多线程环境下被并发修改快慢指针可能表现出非常奇怪的行为比如快指针刚读到的 next 被另一个线程改成了别处两个指针在拓扑上已经不在同一条链上了再比如遍历过程中链表被整体替换快指针在旧链上、慢指针在新链上永远不可能相遇方法会一直跑到快指针碰到 null 才结束返回 false但实际数据可能是有环的。彻底解决要靠外部同步比如读的时候加读锁或者干脆用不可变链表每次修改生成新版本让遍历始终看到一份一致的快照。退一步的做法是在遍历前记录链表的版本号或者节点总数遍历结束时校验版本号有没有变变了就重试。哈希表法在并发场景下也不安全HashSet本身不是线程安全的多线程同时插入会导致内部结构损坏读出来的结果完全不可信必须换成并发容器或者加锁代价比快慢指针更高。所以真实工程里的建议是环形检测这类工具方法要么明确约定“调用方保证链表在检测期间不被修改”要么在方法内部加锁。含糊其辞的约定最后一定会出事我在两个不同的项目里都见过因为这条约定没写清楚导致的偶发故障排查成本极高因为问题不可复现。5.4 问题速查表现象最可能原因处理方式抛 NullPointerException循环条件顺序写反或漏判 fast.next改成fast ! null fast.next ! null所有链表都返回 true初始 slow 和 fast 相等while 一次没进比较挪进循环体或改 do-while有重复值的无环链表误报有环哈希法用了 val 做 key或节点重写了 equals改用节点引用 / IdentityHashMap / id()三节点环测试通过四节点环卡死快指针步长改成了 3 或更大步长改回 2单节点自环返回 false方法开头提前 return没考虑 head.next head去掉提前返回或单独判断自环百万节点检测时 OOM哈希表法存了全部节点换快慢指针或分片处理环入口算出来偏了一位环长计数从 0 开始或指针先移动后计数计数初始化为 1先判断后移动偶发结果不一致无法复现链表被并发修改加锁或改用不可变结构6. 工程里的取舍什么时候不该用快慢指针6.1 需要保留现场时选哈希法快慢指针有个天然短板它只告诉你“有没有环”不告诉你“环在哪、从哪个节点开始重复”。虽然可以用 4.4 节的方法再算一次环入口但你拿到的只是位置信息拿不到“这个节点是被谁指过来的”。排查线上问题时这些信息往往比结论本身更重要。哈希表法在这方面有天然优势因为它记录了完整的访问序列。你可以在发现重复节点时把集合里的节点按插入顺序打印出来一眼就能看出环是从第几个节点开始的、环前面的正常链有多长。如果集合用的是LinkedHashSet遍历顺序就是插入顺序连额外排序都省了。这个能力在定位“谁把尾节点的 next 改错了”这类问题时极其有用能直接把排查范围从整个链表缩小到几个节点。所以我的实际做法是生产环境的检测逻辑用快慢指针保证性能和内存排查工具和调试接口用哈希表法保证信息量。两套代码并存成本不高收益很大。6.2 只读与内存受限场景选快慢指针有些场景下链表是只读的比如从网络接收的序列化数据、内存映射文件里解析出来的结构、共享内存里的节点数组。这类数据你不能修改也不能假设它的大小哈希表法的 O(n) 内存就成了硬约束。一个 512 MB 内存的容器处理一条千万级节点的链表哈希表法直接就没法跑快慢指针毫无压力。还有一种场景是检测逻辑被放在高频路径上比如每次请求都要校验一次参数链表的完整性。这种时候哪怕单次只多花几毫秒乘以 QPS 之后也是可观的 CPU 开销。快慢指针的常数因子小指令数少对 CPU 缓存也更友好因为它是顺序访问而哈希表法的随机访问模式会频繁触发缓存未命中。嵌入式场景更极端栈空间和堆空间都以 KB 计任何动态分配都可能失败。快慢指针只用到两个指针变量没有动态内存分配是唯一可行的方案。这类环境下连递归写法都不能用因为递归深度受栈大小限制链表一长就栈溢出必须老老实实写迭代。6.3 几个真实存在的应用场景抛开面试题不谈环形检测在实际系统里出现的地方比想象中多。第一个是对象图序列化任何支持循环引用的序列化框架内部都得有一张已访问表本质上就是哈希表法只不过 key 是对象引用value 可能是引用编号。第二个是依赖解析模块之间的依赖关系如果形成环构建工具会直接报错而不是死循环靠的就是遍历时的访问标记。第三个是内存池的空闲链表维护某些自制的内存分配器把空闲块串成链表如果某次释放逻辑写错把同一块内存挂了两次空闲链表就会成环后续分配时遍历会卡死。这类问题在嵌入式开发里不算罕见检测手段就是快慢指针因为内存池本身的内存开销必须严格控制。第四个是撤销栈和历史记录某些编辑器的操作历史用双向链表实现如果撤销和重做逻辑处理不当指针可能绕回之前的节点。用户感知到的现象是“按了几次撤销之后界面卡住”排查时用哈希表法打印访问序列能很快定位到是哪次操作把指针接错了。这类问题用快慢指针检测足够但定位还是得靠完整的访问记录。最后再分享一个小技巧。如果你怀疑某条链表有环但不确定又不想写完整的检测代码可以在遍历时加一个计数器超过节点总数的两倍就强制退出并打日志。这个做法不能精确判断但能在不引入任何数据结构的前提下防止死循环适合临时加在线上做兜底。等确认问题存在之后再换成正式的检测逻辑。我在几个老系统里加过这种兜底每次都是先靠它止住故障扩散再慢慢找根因比直接上线一套新逻辑稳妥得多。