Linked List Cycle Detection 应该是链表题里最容易被低估的一道 easy。我第一次刷它的时候看完题觉得“不就是判断有没有环嘛”结果连交三版才过——不是超时就是空指针最后又花了一晚上把所有边界条件串起来才算真正吃透。这篇文章不讲标准答案就讲我踩过的坑、改过的错代码以及最后沉淀下来的一套稳定解法。适合刚接触链表的同学也适合刷过题但每次都要现想边界的朋友查漏补缺。1. 整体思路拆解为什么首选快慢指针而不是哈希表1.1 这个问题到底在考什么题目描述很简短给一个链表的头节点判断链表中是否存在环。即使是 easy 级别它背后也藏着三个考点第一你懂不懂链表这种结构的本质第二你有没有空间复杂度的意识第三你能不能把边界条件处理干净。链表本身是一个线性结构每个节点只知道自己下一个节点是谁。环的存在意味着某个节点的 next 指回了它前面的节点导致遍历永远走不完。这里要注意环不一定是整个链表围成一个圈更常见的是尾部节点指回中间某个节点形成一个“6”字形的结构。LeetCode 的判题系统里判定结果只关心布尔值 true/false但实际工程中遇到循环链表时你往往需要知道环的入口在哪、环有多长所以这道题的价值不在答案本身而在你推导答案的方式。很多教程一上来就贴快慢指针代码这会让新手产生一种错觉——好像背下循环条件就完事了。但刷题的意义恰恰相反你得先理解为什么用快慢指针为什么它能做到 O(1) 空间以及它和哈希表方案的本质区别在哪。否则面试官稍微追问一句“相遇位置一定在环入口吗”很多人就卡住了。1.2 暴力法为什么不可取最容易想到的方案是哈希表从头遍历链表每经过一个节点就把节点引用存进一个 Set如果发现当前节点已经存在说明遇到了环直接返回 true。这个方案的思路非常直白代码也短但它的空间复杂度是 O(n)在最坏情况下需要存下链表里的所有节点。为什么面试场景下不建议第一反应就写哈希表因为面试官会追问“能不能优化到 O(1) 空间”。这道题叫 easy并不是因为它简单到不需要思考而是因为它存在一个优雅的 O(1) 空间解法你能否想到才是关键。另外还有一种更暴力的做法遍历时修改节点的 val 或者给节点打标记遇到标记过的节点就认为有环。这个方案在思路上可行但有三个致命问题。一是它破坏了原链表数据在工程里属于不可接受的副作用二是如果链表节点值本来就允许重复你就无法区分“标记”和“原始值”三是在 LeetCode 上测试时某些用例的节点数据是共享复用的修改值可能影响到其他测试用例的执行。我在本地测试时试过给节点 val 置为特殊值结果跑真实线上用例直接翻车因为输入链表的 val 本来就可以是任意整数特殊值并不特殊。从那以后我再也没用过破坏性方案。1.3 快慢指针的直觉与成本快慢指针也叫 Floyd 判圈算法核心思路是用两个指针同时从 head 出发慢指针每次走一步快指针每次走两步如果链表中有环那么快指针最终会追上慢指针如果没有环快指针会先到达链表末尾。这个逻辑用生活类比最好懂。想象两个人在圆形操场上跑步一个人速度快一个人速度慢。只要跑道是封闭的速度快的人迟早会从后面追上慢的人。而如果跑道是直的速度快的人只会先跑到终点停下永远不会和慢的人相遇。关于快指针为什么“不会跳过”慢指针这里有一个关键点值得展开。很多人担心快指针每次走两步会不会恰好从慢指针头顶跨过去实际上不会。因为两者的相对速度是每一步减少 1 个节点距离而不是 2 个。当快指针在慢指针后面 1 个节点时下一步快指针会到达慢指针现在的位置然后两个指针重叠当快指针在慢指针后面 2 个节点时下一步距离差变成 1再下一步重叠。由于距离差每次只减少 1从任何一个正整数开始最终都会经过 0不会出现从 1 直接跳到 -1 的情况。所以快慢指针的空间复杂度是 O(1)时间复杂度是 O(n)因为慢指针最多走完整个环一圈就会被追上整体遍历次数是线性的。这就是这道题最优解的美妙之处——用极其简单的结构同时满足时间和空间两个维度的最优。我建议你刷这道题的时候先别急着看答案自己画几个链表结构模拟快慢指针的移动过程。画完三个用例之后你对循环条件的理解会比背十遍代码都深刻。2. 核心细节解析三个关键设计决策2.1 快慢指针初始位置的选择第一个细节是快慢指针的起点。最常见的写法是两者都从 head 出发slow head fast head有些教科书里会写成 fast head.next理由是让快指针先走一步这样 while 循环的判断条件可以简化。但这种写法在实现链表环检测时往往需要额外兜底因为你得先确认 head 不为空同时 head.next 也不为空否则 fast 直接做空指针访问。我的建议是统一用 slow head, fast head。理由有三点。第一算法逻辑在起点相同的情况下更简洁循环条件只需要判断 fast 自身以及 fast.next 是否为空即可第二如果链表只有一个节点且无环fast 初始等于 head第一次 while 判断 fast 不为空但 fast.next 为空直接退出循环返回 false逻辑清晰第三当链表有环时起点相同不会影响“相遇”的必然性只是可能会让快指针先绕环半圈再追上慢指针结论完全不变。另一个容易忽略的点是循环条件应该怎么写才安全。正确写法是 while fast and fast.next注意顺序不能反。Python 中 and 是短路运算符如果 fast 是 None就不会再访问 fast.next这样避免了空指针异常。在 Java 或 C 中同样的逻辑写作 while (fast ! null fast.next ! null)。我见过有人写成 while fast.next and fast这个顺序在 Python 里不会报错因为逻辑表达式仍然会先判断 fast.next如果 fast 为 Nonefast.next 会直接抛 AttributeError。所以顺序不是可选的必须把“当前指针本身不为空”放在前面。2.2 while 循环条件的正确姿势循环条件的完整含义是只要 fast 还能走两步就继续推进快慢指针。为什么是 fast 而不是 slow因为 fast 更快它一定是那个先走到链表末尾的指针。如果链表无环fast 终会遇到 None如果链表有环fast 永远不会遇到 None但会追上 slow。这里有一个常见的误判场景有的同学会用 slow 作为循环条件比如 while slow and fast然后循环体内部 slow slow.next, fast fast.next.next。这种写法在无环链表中通常也能跑通但在链表节点数为偶数时fast 可能在 slow 之前变为 None循环条件判断时 fast 为 None 退出返回 false看起来没问题。不过一旦链表节点数为奇数最后一轮循环体内部 fast fast.next.next 会直接触发空指针因为 fast.next 已经为 None你再取 next.next 就崩了。所以大家记住一个口诀判断快指针能不能走两步能走才进循环。我看到很多题解把循环条件写成 while fast and fast.next但很少解释为什么实际使用中这就是避开空指针最关键的一行。另外空链表的情况必须单独考虑。head 为 None 时链表没有环直接返回 false。有些实现会在函数开头写 if not head: return False这是安全处理的一种方式。但如果你把 while 条件写成 while fast and fast.next其实空链表场景也能被覆盖——fast 为 None循环根本进不去直接返回 false。不过为了代码可读性我习惯在开头显式判断一次让后来人不用思考就知道这个函数对空输入做了处理。有一个边界测试用例值得关注链表只有一个节点且该节点的 next 指向自身这是有环的极端情况。此时 fast 为 headfast.next 也是 head两个都不为 None进入循环。第一次迭代后 slow 和 fast 都还是 head相遇返回 true。这个用例能检验你的循环条件是否正确也会暴露一个常见的写法错误——如果循环体内判断相遇的语句放在指针移动之后初次相遇就会错过导致死循环。后面第 4 部分我会专门展开这个问题。2.3 节点值相等不等于找到了环第三个关键设计决策是关于“如何判断找到环”。很多第一次写这道题的人会下意识地比较 slow.val fast.val觉得两个指针停在相同值的节点上就是有环。这个想法在部分测试用例里能侥幸通过但它存在一个逻辑漏洞链表中的节点值并不唯一。举个具体的例子链表 1 - 2 - 3 - 2 - null没有环但节点 2 出现了两次。如果快慢指针恰好都走到了值为 2 的节点你判断为有环结果就是错误的。LeetCode 的测试用例里特意包含这种值重复但无环的链表目的就是考察你比较的是节点本身还是节点值。正确做法是比较指针引用本身即 slow fastPython 比较的是对象身份Java 和 C 比较的都是引用/指针地址。只有两个指针指向同一个节点对象才能说明快指针追上了慢指针这是环存在的充分条件。还有一种写法是给节点加 visited 标记比如在节点对象上挂一个属性判断属性是否存在。这个思路在 JavaScript 或 Python 里可行因为对象可以动态添加属性但它本质上是把空间复杂度变成了 O(n)并且会污染节点数据所以我不推荐在正式解法中使用。记住这道题考的是链表结构和指针关系不是节点数据的值。遇到“值相等”第一反应应该是“需要进一步确认”而不是“找到了”。3. 实操过程与核心环节实现3.1 从错误示例开始一份能跑但会挂的代码为了说明错误学习的过程我先展示一段我早期写过的代码。它结构完整甚至能通过一部分测试用例但边界情况下一定会出问题def hasCycle(head): if not head: return False slow head fast head.next while fast ! slow: if fast is None or fast.next is None: return False slow slow.next fast fast.next.next return True这段代码看似遵循了“快指针先走一步”的常见写法但它有几个隐患。首先是 fast head.next 在 head 只有一个节点时直接是 Nonewhile fast ! slow 这个条件会立刻不成立None ! head 为真然后进入循环体循环体里 if fast is None 会返回 False看起来侥幸通过了。但换一种场景链表有两个节点并且第二个节点的 next 指向第一个节点形成一个环这个实现是否能正确返回 true我们可以推演一下。slow 在 node1fast 在 node2两者不相等进入循环fast 和 fast.next 都不为 None然后 slow 移至 node2fast 移至 node2.next.next也就是 node1.next.next结果还是 node2。此时 slow 在 node2fast 也在 node2循环条件 fast ! slow 为 False退出循环返回 true。这组用例倒是没问题。但是如果链表没有环且节点数为 3也就是 1 - 2 - 3 - Nonehead 为 node1。slow 在 node1fast 在 node2进入循环。fast 不为 Nonefast.next 也不为 None于是 slow 到 node2fast 到 node3.next也就是 None。下一轮 while 判断 fast ! slowNone ! node2 为 True进入循环体if fast is None 成立返回 False。这组也没问题。真正的坑出现在“空链表和单节点无环”场景吗其实上面都覆盖了。但这里有个更隐蔽的问题while 条件本身没有保证 fast 和 fast.next 非空它依赖于循环体内的检查先于指针移动。如果你改了循环体的顺序比如先移动指针再检查就会直接空指针。而且这种写法的可读性很差读者需要仔细推演才知道它“依赖先检查后移动”的隐含约定。后来我把代码重构成了第 2 部分推荐的快慢指针同一起点写法明显简洁且不容易出错。这段经历说明一个道理代码能跑通一部分用例不代表思路可靠你要对每一行的作用都有把握特别是 while 条件和循环体语句的顺序关系。3.2 用 Python 实现正确版本这是我目前最常用的 Python 实现简洁并且边界安全class ListNode: def __init__(self, x): self.val x self.next None def hasCycle(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逐行解释一下关键逻辑。slow head, fast head 是初始化两个指针都指向起点。while fast and fast.next 保证循环体内 fast.next.next 一定安全因为 fast 和 fast.next 都非空。循环体内部先移动指针然后判断 slow is fast。有人会问为什么判断相遇放在移动之后而不是循环开头因为初始状态下 slow 和 fast 都等于 head如果你在进入循环之前先判断一次相等那么无环链表也会因为起点相同而返回 true这显然是错的。所以必须“先推进再判断”让两个指针至少各走了一步才比较。Python 中 is 判断的是对象身份和 不同这正好符合我们比较节点引用的需求。如果你用 那比较的是值也就是 2.3 节里说的陷阱。在 Python 刷题时要养成习惯链表节点判等用 is不要用 。还有一个细节有些题目问的不是“是否有环”而是“返回环的入口节点”那 Floyd 算法需要分为两个阶段第二阶段让 slow 回到 head然后两个指针都每次走一步第一次相遇处就是环入口。这道题 easy 版本用不到这个扩展但建议你顺手了解一下面试经常连环追问。3.3 用哈希表方案做对照为了说明两种方案的差异我再贴一个哈希表实现方便你对比时间复杂度和空间复杂度def hasCycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False这个实现的循环条件只用判断 cur 是否为 None逻辑上确实比快慢指针更直白。但你要记住seen 这个 Set 中存的是节点对象引用不是节点值。这里同样不能写成 cur.val in seen否则值重复必然误判。在 Python 中节点对象默认是按对象身份计算哈希的所以同一个节点第二次出现时cur in seen 会命中而两个值相同但引用不同的节点不会被误判。两种方案的取舍场景如果题目允许 O(n) 空间哈希表更直观也更容易写出正确代码如果面试官要求 O(1) 空间快慢指针是唯一选择。另外哈希表方案还有一个优势它不需要考虑空链表和单节点边界因为 while cur 天然处理了。但哈希表方案在真实面试中的劣势也很明显一旦面试官追问“如果链表非常长怎么办”你回答“用快慢指针”会显得你其实知道最优解但没有第一时间使用。所以我的建议是平时练习时两种都写一遍面试先说快慢指针如果面试官希望看到更直觉的解法再补充哈希表。3.4 测试用例与临界场景写完代码之后我习惯跑一组覆盖边界条件的测试用例。下面是套用标准 ListNode 结构后的实际验证用例列表用例链表结构预期结果说明1Nonefalse空链表21 - Nonefalse单节点无环31 - 1自环true单节点环41 - 2 - 3 - 4 - Nonefalse四节点无环51 - 2 - 3 - 2回到节点2true环在中间61 - 2 - 3 - 1回到头节点true完整环第 5 个用例特别值得注意。它对应链表 1 - 2 - 3 - 2这个结构里节点 2 出现了两次但快慢指针判断的是引用相等所以不会因为节点值重复而误判。第 3 个用例是对循环条件的考验——如果循环条件写错直接进不了循环或者产生死循环。我建议你把这 6 个用例复制到本地跑一遍并用打印语句观察 slow 和 fast 每一步的移动路径。看到“fast 绕了一圈追上 slow”的实际过程比任何文字解释都直观。4. 常见问题与排查技巧实录4.1 我犯过的三个典型错误先说第一个错误让快指针每次走三步甚至更多。我最初的想法是“走快一点不是更快相遇吗”结果在部分无环链表中fast 跳过了链表末尾循环条件判断还以为是快指针正常走到 None却因为跳过了 next 层级而直接空指针。更重要的是如果步长差是 2快指针可能直接从慢指针头顶跨过去导致永远不相遇。快慢指针的数学基础是速度差为 1只有这时候相对距离每次减少 1才必然经过距离 0。步长差不是 1 时是否存在相遇点就变得不可控。所以我后来只用步长差为 1 的组合也就是慢走 1、快走 2。第二个错误是循环条件写成 while fast.next and fast。这个错误在 Python 里非常隐蔽我甚至一度觉得能跑。原因是 Python 的 and 会从左到右计算当 fast 为 None 时fast.next 已经触发异常无论后面怎么写都救不回来。正确的顺序必须是先 fast 后 fast.next。在 Java 或 C 中 也有同样的短路规则判断顺序不对的话fast 为 null 时先访问 fast.next 直接抛 NullPointerException。第三个错误是我把相遇判断放在指针移动之前。前面也提到过因为 slow 和 fast 初始都指向 head如果你在循环开头判断相等无环链表第一轮就会返回 true。正确的做法是在移动之后判断。有一次我在 LeetCode 上提交这种错误版本测试用例返回了“答案错误”我当时完全没反应过来因为直觉上觉得“两个指针在开头就是相等的说明有环吗”显然不是这只是初始状态不是相遇。4.2 快慢指针相遇位置的分析一个高频追问是如果链表有环快慢指针第一次相遇的位置一定是环的入口吗答案是否定的。相遇位置由环的长度、链表的非环部分长度共同决定通常相遇点不在环入口处。以链表 1 - 2 - 3 - 4 - 5 - 3 为例非环部分长度是 2节点 1、2环的入口是节点 3环内节点是 3、4、5环长度为 3。推演一遍slow 走到节点 3 时需要 2 步此时 fast 已经走了 4 步到达节点 5。slow 继续走fast 继续走当 slow 走到节点 4 时fast 走到节点 4当 slow 走到节点 5 时fast 走到节点 5当 slow 走到节点 3 时fast 走到节点 3两个指针恰好相遇在环入口。这个例子看起来很巧但它是巧合不是规律。如果非环部分长度是 3环的入口是节点 4推演结果会是另一个相遇点。理解这一点很重要因为它能帮你解释“为什么返回环入口需要二阶段算法”。第一阶段只负责判断是否有环第二阶段才负责找到环入口。如果你在做扩展题时误认为第一次相遇点就是入口就会得到错误答案。关于“为什么 fast 每次走两步而不是和 slow 相同速度”我再补充一个视角如果快慢指针速度相同它们永远保持初始距离即使有环也不会相遇。快指针的作用是“从后面追”所以必须比慢指针快。速度比为 2:1 是最简单可靠的选择速度比太高会有跳过风险速度比不够快不了多少。4.3 实用建议与扩展刷完这道题有几个小建议和你分享。第一养成先画图再写代码的习惯。链表题最怕直接上手画图能帮你把 next 的指向关系看清楚尤其是环的位置画一遍比想十遍都有效。第二写代码前先问自己三个问题链表可能为空吗链表可能只有一个节点吗如果无环快指针会不会在循环体内变成 None这三个问题想清楚代码里的循环条件基本不会踩坑。第三如果你想验证自己的实现是否正确不要在数组和对象转换上花太多时间可以直接构造链表。我写过一个本地工具函数输入一个节点列表和一个环的起点下标用它构建链表测试非常高效。大概长这样def build_linked_list(values, pos): if not values: return None head ListNode(values[0]) nodes [head] cur head for val in values[1:]: cur.next ListNode(val) cur cur.next nodes.append(cur) if pos ! -1: cur.next nodes[pos] return head这个工具我到现在还在用刷 LeetCode 链表题基本都离不开它。第四个建议是错误记录法。我在本地维护了一个“错误笔记”每次提交出错就把出错原因和对应的测试用例记下来。这道题我记录了三条错误步长差不能大于 1、循环条件顺序不能反、相遇判断必须在移动之后。后来刷其他链表题时很多错误都是这三条的变体查起来非常快。学算法最重要的不是背答案而是弄清楚自己为什么会错。第四个扩展方向是返回环入口。如果你已经掌握了快慢指针我推荐试一下这道题的第二问。做法是第一次相遇后让 slow 回到 headfast 保持在相遇点然后两个指针都每次走一步下一次相遇的位置就是环入口。背后的数学推导不复杂关键变量是“非环部分长度”和“环长度”的模关系。做一遍这个扩展你对 Floyd 算法的理解会直接从“背代码”升级到“懂原理”。第五个扩展是统计环的长度。在第一次相遇后让一个指针原地不动另一个指针每次走一步再次相遇时走过的步数就是环的长度。这个思路和判断是否存在环完全是同一套体系面试中经常作为追问出现。最后再多说一句关于语言差异。Python 中判断节点相等用 isJava 中用 因为比较的是引用C 中直接比较指针地址。很多人在本地用 Python 跑通了到面试写 Java 时还习惯性比较 val这是完全不同的逻辑。刷题时如果有精力最好把同一道题用两三种语言各写一遍这能帮你把“算法思路”和“语言细节”分开避免因为语法细节挂掉面试。我个人在实际操作中的体会是链表类题目是最适合“错误中学习”的类型。它们代码不长但隐藏的边界非常多踩过坑之后很难忘。每次写错了不要急着看题解先自己推演一遍找到出错的那一步把它记下来。等你积累了十几个这种错误点再遇到新题会特别有底气。这个错误笔记的方法比重复刷题有效得多也让我对链表的理解越来越扎实。