链表环检测实战：快慢指针原理、边界条件与常见错误解析

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 为 None，fast.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 为 head，fast.next 也是 head，两个都不为 None，进入循环。第一次迭代后 slow 和 fast 都还是 head，相遇，返回 true。这个用例能检验你的循环条件是否正确，也会暴露一个常见的写法错误——如果循环体内判断相遇的语句放在指针移动之后，初次相遇就会错过，导致死循环。后面第 4 部分我会专门展开这个问题。

2.3 节点值相等不等于找到了环

第三个关键设计决策是关于“如何判断找到环”。很多第一次写这道题的人，会下意识地比较 slow.val == fast.val，觉得两个指针停在相同值的节点上就是有环。这个想法在部分测试用例里能侥幸通过，但它存在一个逻辑漏洞：链表中的节点值并不唯一。

举个具体的例子，链表 1 -> 2 -> 3 -> 2 -> null，没有环，但节点 2 出现了两次。如果快慢指针恰好都走到了值为 2 的节点，你判断为有环，结果就是错误的。LeetCode 的测试用例里特意包含这种值重复但无环的链表，目的就是考察你比较的是节点本身还是节点值。

正确做法是比较指针引用本身，即 slow == fast（Python 比较的是对象身份，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 只有一个节点时直接是 None，while fast != slow 这个条件会立刻不成立（None != head 为真，然后进入循环体），循环体里 if fast is None 会返回 False，看起来侥幸通过了。但换一种场景：链表有两个节点并且第二个节点的 next 指向第一个节点，形成一个环，这个实现是否能正确返回 true？我们可以推演一下。slow 在 node1，fast 在 node2，两者不相等，进入循环，fast 和 fast.next 都不为 None，然后 slow 移至 node2，fast 移至 node2.next.next，也就是 node1.next.next，结果还是 node2。此时 slow 在 node2，fast 也在 node2，循环条件 fast != slow 为 False，退出循环，返回 true。这组用例倒是没问题。

但是如果链表没有环且节点数为 3，也就是 1 -> 2 -> 3 -> None，head 为 node1。slow 在 node1，fast 在 node2，进入循环。fast 不为 None，fast.next 也不为 None，于是 slow 到 node2，fast 到 node3.next，也就是 None。下一轮 while 判断 fast != slow：None != 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 结构后的实际验证用例列表：

第 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 回到 head，fast 保持在相遇点，然后两个指针都每次走一步，下一次相遇的位置就是环入口。背后的数学推导不复杂，关键变量是“非环部分长度”和“环长度”的模关系。做一遍这个扩展，你对 Floyd 算法的理解会直接从“背代码”升级到“懂原理”。

第五个扩展是统计环的长度。在第一次相遇后，让一个指针原地不动，另一个指针每次走一步，再次相遇时走过的步数就是环的长度。这个思路和判断是否存在环完全是同一套体系，面试中经常作为追问出现。

最后再多说一句，关于语言差异。Python 中判断节点相等用 is，Java 中用 ==（因为比较的是引用），C++ 中直接比较指针地址。很多人在本地用 Python 跑通了，到面试写 Java 时还习惯性比较 val，这是完全不同的逻辑。刷题时如果有精力，最好把同一道题用两三种语言各写一遍，这能帮你把“算法思路”和“语言细节”分开，避免因为语法细节挂掉面试。

我个人在实际操作中的体会是，链表类题目是最适合“错误中学习”的类型。它们代码不长，但隐藏的边界非常多，踩过坑之后很难忘。每次写错了，不要急着看题解，先自己推演一遍，找到出错的那一步，把它记下来。等你积累了十几个这种错误点，再遇到新题会特别有底气。这个错误笔记的方法比重复刷题有效得多，也让我对链表的理解越来越扎实。