环形链表判环：从哈希表到快慢指针，详解Floyd判圈算法

说实话，刷到 Hot100 第 22 题的时候，我心里是有点轻视的——环形链表，这题名听着太基础了，第一反应就是“哈希表嘛，遍历一遍记个地址就行”。但后来在一次模拟面试里被面试官追问了一句“不用额外空间怎么做”，我当场愣住，才意识到这题藏着一个特别经典的快慢指针思想，也就是 Floyd 判圈算法。后来我把两种解法、边界条件、证明过程，甚至扩展题 142 都完整啃了一遍，才发现这题虽然标着 Easy，考点密度却一点都不低。

这篇就把我完整的做题过程和思考整理出来，包含完整代码、复杂度分析、面试现场怎么讲、以及大概率会被追问的找环入口推导。无论你是刚入门算法题的新手，还是准备跳槽面试需要快速过 Hot100 的老手，这篇应该都能给你省不少时间。

1. 题目卡点和核心思路拆解

1.1 题目到底在考什么

题目本身就一句话：给定一个链表的头节点 head，判断链表中是否有环。如果有环，返回 true；没有环，返回 false。

很多人第一眼觉得这题简单，但它真正考的东西其实很具体：链表节点的存储特点和指针追及问题的数学直觉。链表在内存里是一串节点，每个节点有一个 next 指针指向下一个节点地址。如果链表中存在环，就意味着某个节点的 next 指针指向了之前已经出现过的某个节点，从那里开始，遍历会永远循环下去，形成一个封闭的环。

这里有个容易踩的坑：环的存在跟节点值完全无关，判断条件必须基于节点的引用（内存地址），而不是节点上存的值。两个不同节点可以有相同的 val，这时如果用值去判重，就会得到错误结果。LeetCode 上给的链表节点结构大概是这样：

class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }

题目要求返回布尔值，但实际面试时面试官往往不会停留在“会不会做”这个层面，而是会追问“为什么快慢指针一定相遇”“空间复杂度能不能做到 O(1)”“能不能找环的入口”。这题就像一个入口，背后牵扯出一整套链表问题的解题框架。

1.2 先说结论：两种解法，一个玩空间，一个玩时间

这题的标准解法就两个方向，理解它们的差异比背代码重要得多：

• 哈希表法：遍历链表，每经过一个节点就把它的引用存进一个 Set，如果遇到某个节点已经在 Set 里，说明存在环。时间复杂度是 O(n)，空间复杂度也是 O(n)。
• 快慢指针法：维护两个指针，slow 每次走一步，fast 每次走两步。如果链表没有环，fast 会先到达末尾；如果有环，fast 和 slow 一定会在环内某一处相遇。时间复杂度 O(n)，空间复杂度 O(1)。

两种方法的取舍很清楚：哈希表法直观、代码简单、不容易出错；快慢指针法空间更优，而且是面试官更想听到的解法。大部分 LeetCode 官方题解，以及各大厂面试的标准答案，都会默认你会快慢指针。所以哈希表应该是你脑中第一个跳出来的思路，但快慢指针才是你真正要写进简历的解法。

1.3 一个重要的前置心智模型

在写代码之前，我建议你先建立一个心智模型：链表不是一条“线”，而是一串内存地址的链式结构。当你遍历链表时，指针是在“节点地址”之间移动，而不是在“值”之间移动。这个模型有助于你理解为什么哈希表存的是节点引用，以及为什么快慢指针的相遇判断可以精确到地址相同。

从这个角度去看，环形链表本质上是一个“指针是否会回到已访问地址”的问题。哈希表法用额外的空间记录“已访问地址”；快慢指针法则利用“不同速度在封闭环内必然追及”的数学性质，省掉了记录空间。后面的所有代码，都是围绕这两个视角展开的。

2. 解法一：哈希表，最简单也最容易想到

2.1 哈希表解法原理

哈希表法的思路非常符合直觉。你可以想象成走迷宫的时候，每到一个路口就把门牌号记在本子上。如果走着走着发现当前门牌号在本子上已经出现过，那就说明你绕回到了已经走过的位置，前面是一个死循环。

具体到链表就是：初始化一个空的哈希集合，从 head 开始遍历，每到一个节点就检查这个节点的引用是否已经在集合里。如果在，直接返回 true；如果不在，就把节点引用加进集合，然后继续走。如果遍历到 null，说明链表走完了也没遇到重复节点，返回 false。

这里我再强调一次：集合里存的是节点对象本身的引用。Java 的 HashSet 会调用对象的 hashCode 和 equals 方法，而 ListNode 默认的 hashCode 是基于内存地址的，所以存引用天然能区分不同节点。如果你自作聪明去存 val，一旦链表里有重复值，结果就是错的。

2.2 Java 代码实现，带注释走读

public boolean hasCycle(ListNode head) { // 记录已经访问过的节点引用 Set<ListNode> seen = new HashSet<>(); ListNode p = head; while (p != null) { // 如果当前节点之前出现过，说明存在环 if (seen.contains(p)) { return true; } seen.add(p); p = p.next; } // 遍历到链表终点，说明没有环 return false; }

这段代码逻辑非常直白，唯一的注意点是Set<ListNode>的泛型类型必须是 ListNode，而不是 Integer。只要节点是同一个对象，哈希集合就能识别出来。

2.3 复杂度与隐藏的问题

哈希表法的复杂度分析很简单：

• 时间复杂度：O(n)，最坏情况下需要遍历所有节点才得出结果。
• 空间复杂度：O(n)，最坏情况下所有节点都被放进集合，占用与节点数成正比的内存。

表面上看起来，这个解法“稳”，但问题也就出在空间上。当链表长度达到几万甚至几十万节点时，额外开一个 HashSet 的内存开销并不小。而且在算法面试里，凡是题目考查“链表 + 环”这个组合，面试官基本都会要求你给出 O(1) 空间的方案。如果一上来就只会哈希表，很容易被判定为“思路比较基础”。

2.4 什么时候该放弃哈希表优先考虑双指针

我的建议是：如果面试官没有提任何限制条件，哈希表法是很好的第一回答，因为它最直观，能体现你能够快速给出一个正确解法。但当面试官追问“能不能优化空间复杂度”时，你就要立刻意识到他期待的答案是快慢指针。这时候就不要再去纠结哈希表的常数优化了，直接转向快慢指针才是正路。

还有一种情况也该优先用快慢指针：当链表长度很大、内存紧张，或者你在嵌入式、底层系统中处理链表，O(n) 的空间开销可能是不可接受的。工程上的链表通常不会无限长，但面试考察的本质是你在资源受限时的取舍能力。所以快慢指针不是“炫技”，而是真正有工程意义的解法。

3. 解法二：快慢指针，真正该学的解法

3.1 Floyd 判圈算法是怎么想到的

快慢指针有一个正式的名字：Floyd 判圈算法（Floyd's Cycle Detection）。它的思想来源特别生活化：在一个环形跑道上，如果两个人同时出发，一个人跑得快、一个人跑得慢，那么跑得快的人最终会从后面追上跑得慢的人。在一条笔直跑道上，跑得快的人只会先到终点，永远不会被追上。

把链表类比成跑道，唯一的问题是：快指针必须每次比慢指针多走一步，也就是 fast 每次走两步、slow 每次走一步。这样才能保证两者在环内相对速度是 1，从而在数学上一定能追上。如果你让 fast 走三步、四步，虽然有时候也能相遇，但这个“有时候”就是最大的风险，后面第 5 节我会专门讲这个问题。

3.2 证明：为什么两步一追就一定能碰面

这里需要一点简单的数学证明，面试的时候能讲出来是加分的。为了方便理解，我把证明拆成两步：

第一步：如果链表没有环，fast 每次走两步，它会比 slow 更快到达 null。所以 while 循环会在 fast 或者 fast.next 为 null 时终止，返回 false。这很好理解。

第二步：如果链表有环，slow 进入环之后，fast 一定已经在环里了（因为 fast 跑得快，可能已经绕了好几圈）。此时把环看成一条环形跑道，fast 在 slow 的“前方或者后方某个位置”，两者的相对距离记为 d。由于 fast 比 slow 每秒多走一步，所以每过一个单位时间，两者的距离 d 就会减少 1。当 d 减少到 0 时，两者就在同一个节点上相遇。因为每次减少的是 1，一个正整数总能在有限步内归零，所以相遇一定发生。

这个证明就是 Floyd 判圈算法的核心。面试时你只要把这个逻辑说清楚，面试官基本就会认可你的理解。

3.3 Java 代码实现，带注释走读

public boolean hasCycle(ListNode head) { // 空链表或只有一个节点，不可能成环 if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; // fast 每次走两步，所以要保证 fast 和 fast.next 都不为 null while (fast != null && fast.next != null) { slow = slow.next; // 慢指针走一步 fast = fast.next.next; // 快指针走两步 // 地址相同，说明追上了，存在环 if (slow == fast) { return true; } } // fast 走到链表末端，无环 return false; }

这段代码有几个关键点要说一下。循环条件是fast != null && fast.next != null，因为 fast 在循环体内要访问fast.next.next，如果fast.next本身就是 null，就会出现空指针异常。另外，slow 和 fast 都初始化为 head，然后先移动、后判断，这个顺序也很有讲究，我们第 5 节会单独讲。

3.4 复杂度分析与几个小细节

快慢指针的时间复杂度是 O(n)，空间复杂度是 O(1)。很多资料直接写“时间复杂度 O(n)”，但完整说法是：链表无环时，fast 遍历到末尾，耗时约 n/2 步；链表有环时，slow 进入环后，最多在环内走不到一圈就会被 fast 追上，所以总步数仍然是 O(n)。这里的“最多走不到一圈”可以用一个直觉解释：fast 相对于 slow 每秒缩短 1 单位距离，而两者初始距离最多不超过环长 L，所以追及所需时间不超过 L。面试时可以说“时间复杂度是线性的，具体常数跟环的位置有关，但整体不会超过 O(n)”。

还有一个细节：快慢指针在环内的相遇点，一定在环的入口之后，不会在入口之前。这一点在后续推导环入口时很关键，先留个印象。

4. 实操过程：从读题到提交通过的完整复盘

4.1 边界条件怎么处理

这题虽然简单，但边界条件处理不好照样会出问题，我梳理了三个最容易踩的：

• 空链表：head 为 null，没有节点，必然无环。直接返回 false，不需要进入循环。
• 只有一个节点：head.next 为 null，也必然无环。同样直接返回 false。
• 单节点自环：head.next 指向自身，这种情况下链表只有一个节点，但它确实是一个环。此时快慢指针都从 head 出发，slow 走一步还是回到 head，fast 走两步也会回到 head，两者在第二轮相遇，返回 true。

前两个边界条件我习惯在函数开头统一处理：

if (head == null || head.next == null) { return false; }

这样写既简洁又能避免后面的空指针问题。单节点自环的情况则不需要特殊处理，快慢指针代码本身就覆盖了。

4.2 完整测试用例设计

写算法题不能只满足于“过了 LeetCode 的样例”，我一般会在本地或者脑子里过一套完整的测试用例，确保边界覆盖到位。下面这个表是我自己常用的测试矩阵：

这套用例基本覆盖了所有分支：空、单节点、多节点、环在头部、环在中间、自环、无环。写题时把这些情况在脑子里过一遍，代码的健壮性会明显提高。

4.3 Python 实现有什么不同

国内不少读者用 Python 刷题，Python 版本和 Java 的差别非常小，重点在于判断引用相等时要用is而不是==。==在 Python 中可能会触发对象内容的比较，而我们要的是地址判断，所以必须用is。顺便给一个可以运行的版本：

def hasCycle(self, head: ListNode) -> bool: if not head or not head.next: return False slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False

这段代码在 LeetCode 上可以直接跑通。Python 的代码虽然简洁，但面试手写时要注意类型标注不一定要写全，重点是把逻辑讲清楚。我个人一般先写 Java 版本，因为 Java 对空指针的约束更严格，写的时候会下意识想清楚每一个next是否可能为 null，反而更容易避免边界错误。

4.4 面试现场如何一步步说清楚

面试的时候，建议按照下面这个顺序，由浅入深地表达，效果最好：

1. 先说暴力解：“首先我可以遍历链表，把访问过的节点放进 HashSet，如果遇到重复节点就有环。这样做时间 O(n)、空间 O(n)。”
2. 主动提出优化：“题目如果要求空间 O(1)，我可以用快慢指针：慢指针走一步，快指针走两步。如果没有环，快的会先遇到 null；如果有环，两者最终在环内相遇。”
3. 补充正确性证明：“因为快指针相对慢指针的速率为 1 步/单位时间，每次追 1 个单位的距离，所以有限步内必然追上。”
4. 提边界：“空链表、单节点链表直接返回 false；单节点自环的时候，两个指针走完一轮会相遇。”
5. 写代码，然后自己过一遍测试用例。

这套表达方式的妙处在于：不管面试官接下来追问什么，你都已经把思路、证明、边界全部展示过了，后续对话基本就在你的节奏里。我第一次模拟面试时只说了代码，没有讲证明，结果被追问“你怎么证明一定相遇”时卡住了。后来我把证明补上，整个回答的完成度完全不一样。

5. 常见问题与避坑：踩过才懂的点

5.1 快指针走三步行不行？我劝你老实走两步

这是我在学习过程中产生过的最大的疑问：既然 fast 走两步能追上，为什么不能走三步、四步，这样不是更快吗？实际测试下来，走三步在部分情况下确实能相遇，但无法保证在所有环形链表上都相遇。

背后是数学上的同余问题。设环的长度为 L，快指针每单位时间走 k 步，慢指针走 1 步，速度差 d = k - 1。假设某一时刻两者的相对距离为 r，那么二者相遇的数学条件是：存在整数 t 使得 r + d·t 能被 L 整除。这个同余方程等价于 d·t ≡ -r (mod L)，有解的充要条件是 gcd(d, L) 能整除 r。标准解法中 d = 1，任何 r 都能被 1 整除，所以一定相遇。而如果你让 fast 走三步，d = 2，如果环长 L 是 4，初始相对距离 r 是奇数，gcd(2, 4) = 2 无法整除 r，则永远不可能相遇。

所以面试时千万不要自作聪明写 fast = fast.next.next.next。标准答案就是两步一步，因为只有这个速度差能保证判断绝对正确。

5.2 死循环和空指针是怎么出现的

快慢指针写法有一个常见的隐藏 BUG：先判断等于 head，再移动。假设你把判断写成：

while (fast != null && fast.next != null) { if (slow == fast) { return true; } slow = slow.next; fast = fast.next.next; } return false;

这个写法在普通无环链表上没问题，但在单节点自环时，初始 slow 和 fast 都等于 head，while 循环一进去就直接命中slow == fast，返回 true，结果某种程度上依然正确。真正的问题出在有环但入口不在 head 的链表上——初始判断的时候 slow 和 fast 都在 head，这个判断并没有做错，但会误导你忽略一个事实：判断相遇应该放在移动之后。因为初始时两个指针本来就在同一个起点，这个“相遇”毫无意义。

更经典的错误是循环体内先判断fast.next.next而忘记检查fast.next是否为 null。如果链表长度是奇数，fast 走到最后一个节点时，fast.next为 null，此时再去取fast.next.next就会抛 NullPointerException。所以必须把fast != null && fast.next != null同时写在 while 条件里。

5.3 哈希表法的隐性限制

哈希表法也有一个容易忽略的点：两个不同节点可能拥有相同的值，所以集合里必须存节点引用。如果你误存了ListNode.val，当链表中有两个值为 3 的不同节点时，第二个就会被误判为“已经出现过”，从而把无环链表判成有环。

另外，Java 的HashSet<ListNode>是因为 ListNode 默认equals才达到正确语义的。如果你在真实工程里自定义了一个重写了 equals 的链表节点类，用哈希表判环前就要想清楚这个 equals 是基于值还是引用。基于值的 equals 在这个场景下会让哈希表法失效。这也是我为什么强调“理解哈希表存的是引用”比记住代码更重要的原因。

6. 进阶：这题背后还能挖出什么

6.1 变体题：找环入口（142 题）原理推导

Hot100 里紧接着就有一道关于环形链表的变体题：142. 环形链表 II，要求返回链表中环开始的节点。很多同学背下了代码，但不理解为什么相遇后把一个指针放回头节点，再同步走一次就能找到入口。这里我把推导写清楚，建议收藏。

设链表中 head 到环入口的距离为 a；环入口到快慢指针相遇点的距离为 b；相遇点到环入口的距离为 c；环长为 L = b + c。

慢指针从 head 到相遇点一共走了 a + b 步。快指针速度是慢指针的 2 倍，所以它走的距离是 2(a + b)。同时，快指针走的路程也可以写成：a + b + kL，其中 k 表示快指针在相遇前绕了 k 圈。于是有：

2(a + b) = a + b + kL

进一步化简：

a + b = kL

再代入 L = b + c：

a = kL - b = (k - 1)L + c

这个式子的含义是：从 head 走到环入口的距离 a，等于从相遇点继续走 c 步（绕了 k-1 圈之后）的距离。因此推导出解法：第一次相遇后，把一个指针放回 head，另一个留在相遇点，两者都以步长 1 移动，再次相遇时的节点就是环入口。

这个推导我建议你亲自在草稿纸上画一遍图，半个月后都不会忘。面试现场能当场推导出来的候选人，通常都能给面试官留下很好的印象。

6.2 工程场景里的环形链表

你可能觉得链表判环只是个面试题，实际工程中用得不多。其实环形结构在系统设计里非常常见：CPU 调度里的循环队列、网络数据包的环形缓冲区、某些缓存淘汰算法里的循环链表，都是“链表 + 环”的形态。当这些结构出现异常，比如某个 next 指针被错误地指回之前的位置，就会导致死循环、CPU 占用飙升、服务卡死。

我在定位线上问题时确实遇到过一次类似的现象：某个消息队列消费者线程一直不退出，日志刷个不停，最终定位下来是队列的某个节点被错误改写了 next 指针，形成了一个意外的环。那时候我才真切感受到，判环不只是一个算法题，它也是一种排查无限循环问题的通用思路。就算链表不大，指针故障引发的服务异常也可能很严重，掌握这个工具相当于给自己储备了一个应对循环问题的检测手段。

另外，不断轮询的 DNS 负载均衡、循环链表实现的进程调度等场景，天然就需要能正确识别“这个环是我想要的，还是异常产生的”。所以把快慢指针吃透，对后面的系统设计面试也有帮助。

6.3 一个刷题方法论的建议

最后分享一个我自己刷题的方法：凡是链表题，一律先在纸上画图，标出每个指针的位置变化，再写代码。尤其是环形链表这种需要“动态追及”的题目，光靠脑子想很容易漏边界，画图之后每一步都很清楚。

具体做法是：画一条链表，把 slow 和 fast 的当前位置用两个不同颜色的点标出来，然后逐步推进，模拟 3 到 5 步。你会直观地看到 fast 进入环、slow 后进入环、两者距离逐步缩短直到相遇的完整过程。这个习惯帮我解决的不只是 141 和 142，还包括后面一大堆链表操作题，比如反转链表、合并有序链表、删除倒数第 N 个节点。链表题本来就依赖空间想象，多画图不会亏。

第二点建议是：不要只满足于“提交通过”。LeetCode 上通过这一题很容易，代码也不长，内核是快慢指针的理解和 142 的推导。这两个点才是这题真正的价值所在。如果你能顺手把相遇点、环入口、环长这些相关量之间的关系都推导一遍，那这题就刷得很值了。

我个人刷完这题的感觉是：看答案一分钟，理解证明才是真正的收获。把“为什么相遇”从直觉上升到数学结论之后，再遇到类似的追及类问题，就会有一种通了的感觉。希望你也能体会到这种从“看懂代码”到“真正掌握”的转变。