金宇澄“这题我会，写个快慢指针不就完事了。”
结果面试官多问一句“为什么快慢指针一定能相遇？相遇之后为什么从头再走一个指针就能找到入口？”——当场卡住。
LeetCode Hot 100 里的第 25 道题《环形链表》，算是刷题路上最容易“背会答案但说不出道理”的题目之一。题干很短，解法也很短，但题目背后藏着的 Floyd 判圈算法、数学推导、边界条件处理，才是面试真正想考的。这篇就用拆题的方式，把环形链表从暴力解法到最优解、从代码到证明，原原本本捋一遍。
适合准备算法面试的人、刚开始刷 LeetCode 的初学者，以及那些“已经 AC 了但总觉得哪里没学透”的同学。
1. 环形链表这题，到底在考你什么
1.1 题目描述拆开看
题目原话大致是：给你一个链表的头节点，判断链表中是否有环。如果链表中有某个节点的 next 指针连续追踪之后又回到了之前的节点，说明存在环。
我给你换个说法。你手里一根链条，本该从头串到尾，但中间某个节点的指针没有指向链表尾部的空节点，而是回头指到了链表中一个更靠前的节点。这样一来，你顺着链条往前走，就会陷入一个循环永远出不去。题目要你判断的，就是这跟链条里有没有这种“回环”。
这个判断听起来简单，但有个隐含约束：你只能拿到头节点，不知道链表的长度，也不知道环在哪里。 而且链表的节点不是数组，你不能按下标随机访问，只能顺着 next 指针一个个走。这就排除了很多“先数长度再判断”的朴素思路。
1.2 三类人面对这道题时的不同处境
第一类是刚入门的新手。 拿到题第一反应是遍历，然后把每个节点存下来，走到某个节点发现以前存过，那就有环。这个思路完全正确，能跑通，但它用了额外空间。面试官一般会追问：“能不能不用额外空间？”
第二类是背过答案的同学。 知道快指针一次走两步，慢指针一次走一步，一个 while 循环，相遇就是有环。代码默写得很流畅，但被问到“为什么慢指针走一步、快指针走两步一定会相遇？”时会愣住。
第三类是真正理解的人。 能讲清相对速度的概念、能推导入口点的数学关系、能顺手解决《环形链表 II》那个找入口位置的进阶版。面试官问完最后一句话，通常会得到一个“不错”的评价。
我见过太多人停留在第二类。在面试里，这其实是最危险的状态——因为代码题最怕的不是写不出来，而是“你写出来了，但答不清楚为什么”。这会让面试官怀疑你是背题背出来的。这篇文后面很大一部分篇幅，就是在解决这个问题。
1.3 一个必须先纠正的直觉误解
很多人以为“环”必须是个完整的圈，比如链表里有一整段循环结构。其实不是。只要链表里任何一个节点的 next 指向了它自己或者之前任意一个节点，整个链表就有了环。
举个例子，一个只有两个节点的链表，每个节点的值都是 1，形状是：
code复制节点A -> 节点B -> 节点A
这是环。节点B的next指向节点A，你在A和B之间转圈。
再看另一个例子：一个单节点链表，它的 next 指向自己，也是环。这是一个“自环”，也是典型的环。
理解了这一点，你对“环”的定义才会真正清晰：环的本质不是循环的圈有多长，而是某个 next 指针“回头”了。
我们写判空逻辑时，也必须考虑这些极端形态——比如链表只有一个节点时，如果它的 next 指向了它自己，快慢指针同样能判断出来。我们后面会专门讲边界条件。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 哈希集合解法：一道人人都能想到的安全牌
2.1 核心思路与完整代码
先别急着上最优解。咱们第一次见到这道题，最自然、最不容易出错的思路其实是“遍历 + 记录”。
每经过一个节点，就把这个节点的引用（不是值，是引用，这点极其重要）存进一个集合里。如果遍历过程中发现某个节点的引用已经在集合里，那说明它被访问过两次，链表有环，直接返回 True。如果遍历到了空指针，说明链表走到了头，没有环。
Python 代码如下：
python复制def hasCycle(head):
seen = set()
cur = head
while cur is not None:
if cur in seen:
return True
seen.add(cur)
cur = cur.next
return False
Java 版本也很简单：
java复制public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<>();
ListNode cur = head;
while (cur != null) {
if (seen.contains(cur)) return true;
seen.add(cur);
cur = cur.next;
}
return false;
}
2.2 为什么存引用而不是存节点的值
这是哈希解法里最容易犯的错误：把 node.val 存进 set，而不是把 node 本尊存进去。
链表节点的值不唯一。比如一个没有环的链表里，可能有 10 个节点的值都是 0。如果你按值判断，走到第二个值为 0 的节点时，set 里已经有 0 了，你会误判为有环。这属于经典的“拿属性当身份”的错位。
正确的做法是存引用。在 Python 里，ListNode 对象作为不可变哈希对象存进 set；在 Java 里，HashSet
提示：这也从侧面解释了为什么链表判断环的问题不能用“标记数组”按节点下标来做——你没有下标，唯一的身份标识就是对象引用本身。
2.3 复杂度与面试官的“不够优雅”
哈希集合解法的时间复杂度是 O(n)，空间复杂度也是 O(n)。n 是链表节点数。
空间 O(n) 带来的问题在于，如果这个链表特别长，比如有上亿个节点，你要额外存上亿个引用，内存开销很可观。更关键的是，面试官问这道题，就是想考察你能不能想到“巧妙的办法去掉额外空间”。如果你一上来就写哈希解法，大概率会收到一句：“能不能再优化一下？比如不用额外空间？”
然后才是快慢指针的出场时机。
不过哈希法在面试里也不是一无是处。如果你先讲出哈希法、分析它的复杂度，再自然过渡到“我们可以用 O(1) 空间做到”，这反而是一种很漂亮的回答路径。 面试官会觉得你思路是递进的，而不是背题的。
3. 快慢指针判环：Floyd 判圈算法的直觉与代码
3.1 相对速度：为什么一定会相遇
快慢指针的思路可以用一个生活场景说清楚。
想象一条环形跑道，两个人同时从起点出发。一个人跑得快，一个人跑得慢。在只有环、没有起点到环入口那一段路程的情况下，快的人一定会从后面追上慢的人。哪怕慢的人也在跑，快的人每跑一段就会和慢的人相遇一次。这就是“相对速度”的概念——快的人相对慢的人，每单位时间多跑一段固定的距离，这个距离不断累积，最终追平。
快慢指针就是把这个生活画面抽成了算法。慢指针每次移动一步（slow = slow.next），快指针每次移动两步（fast = fast.next.next）。如果链表中没有环，快指针会先到达链表尾部，遇到空节点，算法结束。如果链中有环，两个指针都会进入环内，在一个“永远不会遇到空节点”的闭环里转。因为快指针相对慢指针每轮多走一步，所以它必然会在有限时间内和慢指针相遇。
这个“有限时间”如何保证呢？当两个指针都在环内时，假设环的长度是 L。快指针相对慢指针的距离每轮缩小 1，而它们的初始距离不可能超过 L，所以在 L 轮以内必定追上。
直观结论就是：只要链表有环，快慢指针一定会相遇。如果链表无环，快指针会先触及终点空指针。
3.2 快指针步长为 2 是最差情况的最优选择
你可能好奇：为什么约定俗成是“慢 1 快 2”？快指针不能一次走 3 步、走 4 步吗？
技术上，步长为 3 也能判环，因为相对速度变成 2，依然会在有限轮内追上。但是步长选 2 有两点好处：
第一，匹配度最好。环的最小长度可能是 1（自环），也可能是 2。如果快指针步长大于环长，它可能每一次都“跳过”慢指针所在的那个节点，不过就算这样，只要继续转，依然能追上。为什么不怕错过？因为两个指针都在持续运动，快指针是满环地转，慢指针也在走，只要相对距离每轮缩小 k-1（k 是快指针步长），总有一个时刻距离归零。选 2 时，相对距离每轮缩小 1，是最平滑的收敛方式，推导也最简洁。
第二，代码最简单。fast.next.next 只需要确保 fast 和 fast.next 不为空，不用考虑更多层的空指针访问。
3.3 判定代码的标准实现
先看最终版的判定代码，再逐行解释。
Python：
python复制def hasCycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
Java：
java复制public boolean hasCycle(ListNode head) {
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;
}
为什么 while 条件是 fast 和 fast.next 都不为空？
因为循环体里要访问 fast.next.next。如果 fast 本身是空，访问 fast.next 会异常；如果 fast.next 是空，访问 fast.next.next 会异常。所以循环开始前必须同时确认这两层节点都存在。如果 fast 或 fast.next 为空，说明链表中某个位置已经到达尾部，链表没有环。
为什么慢指针从 head 出发，先走的是 slow.next？
slow 和 fast 初始都在 head。在循环里，先让 slow 走一步、fast 走两步，然后判断是否相等。如果一开始就相等，那 head 还没开始走就相等了，这没意义。所以必须先移动后比较。
有的实现会把“先移动后比较”改成“先比较后移动”的变体，但不推荐，容易在空链表和单节点链表上出错。按先移动后比较这个顺序写是最稳的。
3.4 为什么“无环链表”时这个代码一定不会死循环
每次循环，fast 都会向前走两步。如果链表没有环，fast 迟早会走到 null 或 fast.next 为 null 的位置。此时 while 条件失败，循环退出，返回 False。不存在无限循环的可能，因为 fast 的移动是向前的，它朝链表尾部收敛。
你也别担心 slow 为空的问题。因为 fast 比 slow 移动快，fast 都没走到尾部，slow 也不会在 fast 到达尾部之前变为空。慢指针最多到达尾部前一个节点就被停止，不会越界。
4. 环入口点的数学证明：相遇之后还要再走一圈
如果只需要判断“有没有环”，上面的代码已经结束了。但 LeetCode 的进阶题目《环形链表 II》（第 142 题）还要你返回环的入口节点。很多同学在刷 Hot 100 时只刷了第 25 题，没刷第 142 题，面试被追问时就会吃亏。
4.1 关键三步推导
我们设几个变量来描述链表结构：
- 从链表头（head）到环入口节点的距离为
a。 - 从环入口节点到快慢指针相遇点的距离为
b。 - 从相遇点继续沿着环走到环入口的距离为
c。 - 环的长度
L = b + c。
两个指针从 head 同时出发，慢指针到相遇点走的路程是 a + b。
关键是快指针。快指针速度是慢指针的两倍，在相同时间内走的路程是慢指针的两倍，也就是 2 * (a + b)。但快指针追上慢指针之前，它可能已经在环里转了好几圈。设它从环入口进来后绕了 k 圈整（k 是非负整数），到达相遇点时走的总路程可以写成：
code复制a + k * L + b
其中 a 是头节点到环入口，k * L 是绕的整数圈，b 是环入口到相遇点的部分。因为快指针到达相遇点肯定是在入环之后，所以它的路程可以这样分解。
两倍关系给出等式：
code复制2 * (a + b) = a + k * L + b
移项化简：
code复制a = k * L - b
因为 L = b + c，所以：
code复制a = k * (b + c) - b
继续化简：
code复制a = (k - 1) * (b + c) + c
这个式子的意思是：从头节点到环入口的距离 a，等于从相遇点继续绕 k-1 圈整后再走 c 步的总距离。
4.2 这个等式告诉你一个非凡的结论
我们来看 a = (k - 1) * L + c 这个结论。如果让两个指针从两个位置同时出发：一个从链表头 head 出发，另一个从相遇点出发，每次都走一步，那么它们最终会在哪里相遇？
从头出发的指针走了 a 步到达环入口。从相遇点出发的指针走了 a 步——这个 a 步等价于走了 k-1 圈整环再加上 c 步。相遇点再走 c 步，正好也到环入口。走完整数圈之后，它依然回到相遇点之前的位置，再走 c 步，就在环入口。
所以结论是：让一个指针从链表头部重新出发，让另一个指针从快慢指针相遇点继续出发，两者都每次走一步，它们必定在环入口处相遇。
这个证明就是《环形链表 II》题解的理论基础。
4.3 找入口的完整代码
Python 版本：
python复制def detectCycle(head):
slow = head
fast = head
has_cycle = False
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
has_cycle = True
break
if not has_cycle:
return None
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
Java 版本：
java复制public ListNode detectCycle(ListNode head) {
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;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
注意这段代码里有个隐蔽的细节：第二次循环用的是 slow = head 而不是再新建一个指针。原因是原来的 slow 还在相遇点。把 slow 拉回 head，让它从头走；fast 留在相遇点继续走。两者步长都是 1，最终在入口相遇。返回 slow 就是入口节点。
从复杂度上讲，第一次循环是 O(n)，第二次循环最多也是 O(n)，总时间 O(n)，空间 O(1)。
5. 几个真实提交中常见的坑
5.1 空链表与单节点链表
很多人看到这道题，测试用例给了个 []，直接懵了。其实空链表没有环，直接返回 False。单节点无环链表返回 False，单节点的 next 指向自己是有环，返回 True。
快慢指针代码对这两种情况天然正确。空链表时 fast 是 None，根本进不了 while 循环，返回 False。单节点 self-loop 时，循环会执行：slow 到自身，fast 到自身（fast.next.next 指向同一个节点），然后 slow 与 fast 相等，返回 True。
5.2 快指针访问层级的问题
这是 LeetCode 提交里最经典的报错来源，常见错误写法：
python复制while fast.next is not None and fast.next.next is not None:
或者只判断 fast：
python复制while fast is not None:
第一种写法在 fast 本身为 None 时，直接访问 fast.next 就崩了。第二种写法在 fast 接近链表尾部时，循环体里访问 fast.next.next 可能会访问到 None.next，同样崩溃。
正确写法必然是：
python复制while fast is not None and fast.next is not None:
利用 Python 的“短路求值”，先看 fast 是不是 None，再看 fast.next 是不是 None。这一步保证了 fast.next.next 的安全访问。
5.3 比较引用，不要比较值
快慢指针相遇的判断：
python复制if slow is fast:
这里的 is 比较的是对象引用，而不是节点值。如果用 slow.val == fast.val 来判断，会怎样？会出现两个不同的节点恰好有相同的值，程序误判有环；更离谱的是，两个指针指向同一个节点但值相同，返回 True 没问题，但两个不同节点值相同也返回 True，就是错的。
这一点和哈希解法里“存引用而不是存值”是同一个道理。
5.4 入口检测中死循环的隐患
如果确认链表有环，第二次循环肯定能找到入口。因为根据数学推导，两个指针必然在入口相遇。但如果链表没有环而你贸然执行第二次循环，fast 和 slow 永远不可能相遇，会陷入死循环。所以第二次循环必须在确认有环之后才执行。代码里用 if not has_cycle: return None 拦截了这种情况。
5.5 极端大环的考验
有一种测试用例很喜欢构造“超大环”，比如链表中前 10000 个节点是直链，后面 50000 个节点组成环。快慢指针在这种用例上运行速度很快，因为总共只要走 O(n) 步。但如果是用递归判断环，直接就栈溢出了。这也是这道题考察“迭代而非递归”的重要原因之一。
6. 从环形链表到同类问题：一种思想的复用
6.1 LeetCode 142：环形链表 II
前面已经写过完整代码。它与第 25 题的区别在于，返回入口节点而不是布尔值。面试时能把这两题打通讲，是很大的加分项。你会发现第 142 题完全是第 25 题的“证明 + 扩展”。
6.2 LeetCode 202：快乐数
“快乐数”问题是环形链表思想的神奇迁移。规则是：对一个正整数，不断求各位数字的平方和，如果最终能变成 1 就是快乐数，如果陷入了不是 1 的循环，就不是快乐数。
你会发现，这个“不断计算平方和”的过程，本质上也是一个“按规则跳转”的链表式遍历。数字变成下一个数字，就像 node 变成 node.next。如果某次计算重复，就说明进入了环。于是快乐数问题可以转化成：在一条虚拟链表里，用快慢指针判环。
解法：
python复制def isHappy(n):
def get_next(x):
total = 0
while x > 0:
digit = x % 10
total += digit * digit
x //= 10
return total
slow = n
fast = get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1
这题在 Hot 100 里可能不会优先刷到，但面试问“你还能想到什么类似题目”时，能用它展示你对算法的理解深度。
6.3 快慢指针思想还能用在链表中点
面试官如果顺着环形链表往下问，还有一个高频变体：寻找链表的中点。
比如 LeetCode 876《链表的中间结点》。解法同样是快慢指针：快指针每次走两步，慢指针每次走一步，快指针到终点时，慢指针恰好在中点。
python复制def middleNode(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
这个应用在很多面试场景中会突然出现，比如“判断回文链表”就经常配合这个找中点的方法使用。你在练习环形链表时顺手把这类题也刷了，性价比很高。
6.4 现实中的应用联想
链表判环的现实对应物很多。比如缓存淘汰算法里，如果某个数据块的引用因为错误操作形成了循环引用，程序就可能陷入无限循环；又比如流程引擎的状态机模型，如果状态转移表里有指向自身或回跳的路径，调度器需要检测这种环，否则任务会卡死在流程里。
你不需要在面试时硬讲这些场景，但如果面试官问“这个算法除了刷题还有什么用”，能从“存在循环依赖的流程检测”角度聊两句，会很加分。
7. 写在最后：我的实操体会
当年我自己刷环形链表这题时，也属于“默写答案”那一档。后来去面试前认真做了证明，再把代码逐行过了一遍边界条件，才发现原来这题藏着这么多细节。
给你两个实操上的小建议：
第一，刷题时把证明过程写一遍，不要只看不写。这题的数学推导并不复杂，但自己动笔推一遍和看别人推一遍，记忆深度完全不同。
第二，提交前用三组特殊用例自测：空链表、单节点、两个节点成环，看代码会不会崩。很多 AC 一次的代码其实只是侥幸通过了主测试，这三组用例一测，各种隐藏 bug 就现出原形。
如果下次面试有人让你做环形链表，别急着写 while 循环。先把“为什么快慢指针一定能相遇”“相遇点如何映射到环入口”这两句话在心里过一遍。能讲出这两件事的人，才算是真正拿下了这道题。