1. 环形链表问题到底在问什么环形链表这道题几乎成了所有技术面试里链表章节的“守门员”。题目本身很短给你一个链表的头节点判断链表里有没有环如果有找出环的入口节点。很多人第一次做的时候脑子里蹦出来的第一个念头就是“拿个哈希表把走过的节点全存下来遇到重复的就是环”这个思路没错但它需要额外的存储空间。而真正让这道题封神的是那个能把空间压到常数的快慢指针解法以及背后那套让无数人第一次看觉得“这也行”的数学证明。我在带新人和做模拟面试复盘的时候发现一个特别有意思的现象大部分人能背出快慢指针的代码但一旦被追问“为什么快指针走两步、慢指针走一步它们一定会在环内相遇”“为什么相遇之后把一个指针放回头部再同速前进相遇点就是环的入口”就开始支支吾吾。这说明大家记住的是结论不是逻辑。而这道题的价值恰恰不在代码本身代码五行就写完了价值全在那套证明过程里。它训练的是你把一个几何运动过程抽象成代数方程的能力这种能力在排查线上死循环、分析状态机、甚至理解某些分布式一致性协议时都会反复用到。这篇文章我打算把环形链表问题从头到尾拆一遍。不管你是刚开始刷题的新手还是已经能默写代码但没深究过证明的老手我都会把每一步的“为什么”讲透。我会先讲清楚问题模型和常见误区然后重点做快慢指针的完整数学证明接着给出可直接复现的代码实现和边界处理最后整理一份我在实际面试和代码审查中遇到的典型问题速查表。整篇内容基于我自己的理解和多次讲解经验所有推导都会给出中间步骤不会跳步。2. 问题模型与常见解法对比2.1 链表节点的结构约定在开始之前先把模型统一一下。我们讨论的链表是单链表每个节点包含一个值域和一个指向下一个节点的指针最后一个节点的指针指向空。环形链表的意思是链表中某个节点的指针不是指向空而是指向了链表中之前出现过的某个节点从而形成一条闭合的环路。注意环不一定从头部开始也不一定包含所有节点。比如一个链表是 1→2→3→4→5→3那么从节点3开始就进入了环环是 3→4→5→3而节点1和节点2是环外的“尾巴”。这个模型里有两个关键量环外部分的长度我记作 a环的长度我记作 b。整个链表的总节点数就是 a b。头节点到环入口的距离是 a环入口到快慢指针相遇点的距离我记作 x那么相遇点到环入口的剩余距离就是 b - x。这些记号在后面证明里会反复用到先建立起来。2.2 哈希表解法直观但费空间最朴素的解法是遍历链表用一个集合记录访问过的节点。每到一个节点先查集合里有没有它有就说明有环且这个节点就是环入口没有就加进去继续走。走到空指针就说明无环。这个解法的时间复杂度是 O(n)因为每个节点最多访问一次。空间复杂度也是 O(n)最坏情况下所有节点都要存进集合。它的优点是逻辑极其直白几乎不会写错面试时如果一时想不出快慢指针用这个至少能拿到基础分。缺点是空间开销大当链表很长时集合会占用大量内存。在实际工程里如果只是偶尔判断一次哈希表完全够用但如果是高频调用的底层函数这个空间开销就不可接受了。2.3 快慢指针解法优雅的常数空间快慢指针的核心思想是设置两个指针慢指针每次走一步快指针每次走两步同时从头节点出发。如果链表无环快指针会先到达空指针此时直接返回无环。如果链表有环快指针会先进入环然后在环内不断绕圈慢指针随后也进入环。由于快指针速度更快它一定会在环内某个位置从后面追上慢指针两者相遇。相遇就说明有环。这个解法的时间复杂度是 O(n)空间复杂度是 O(1)。它的代码非常短但证明过程需要一点数学功底。很多人卡在“为什么一定会相遇”和“为什么相遇点能推出环入口”这两个问题上。下面我用两个小节分别把这两个问题证清楚。2.4 两种解法的取舍逻辑什么时候用哈希表什么时候用快慢指针我的经验是面试场景优先写快慢指针因为它能展示你对指针操作和数学推导的掌握是加分项但如果面试官明确说“先写个能跑的”或者你时间紧张哈希表是稳妥选择。工程场景则要看调用频率和内存约束。如果这个判断逻辑在热路径上被频繁调用快慢指针的 O(1) 空间优势就体现出来了如果只是启动时检查一次配置链表哈希表的可读性反而更好维护。还有一个容易被忽略的点哈希表解法在找到环入口时是直接返回的而快慢指针需要二次追击才能定位入口。所以如果题目只要求“判断有没有环”快慢指针一步到位如果要求“返回环入口”快慢指针需要多一个阶段。这个区别在写代码时要注意。3. 快慢指针相遇的完整证明3.1 为什么快指针一定会追上慢指针先证明相遇的必然性。假设链表有环环的长度为 b。当慢指针刚进入环时快指针已经在环内走了若干圈设快指针此时在环内的位置领先慢指针 k 步0 ≤ k b。这里“领先”是指沿环的前进方向快指针在慢指针前方 k 个节点的位置。接下来考虑两者的相对运动。慢指针每走一步快指针走两步所以每经过一个时间单位快指针相对于慢指针净追近 1 步。也就是说两者之间的距离从 k 开始每个时间单位减少 1。因为 k b而环是循环的所以经过 k 个时间单位后快指针正好追上慢指针两者相遇。如果 k 0说明慢指针刚进环时快指针就在环入口等着直接相遇。这里有一个常见的误解有人觉得快指针走两步可能“跳过”慢指针。比如两者距离为 1 时快指针走两步慢指针走一步会不会快指针从慢指针头上跨过去我们来算一下距离为 1 时慢指针走一步后两者距离变成 0因为慢指针走到了快指针原来的位置不对要仔细算。设慢指针在位置 p快指针在位置 p1沿前进方向。一个时间单位后慢指针到 p1快指针到 p3。此时快指针在 p3慢指针在 p1沿环方向看快指针在慢指针前方 2 步这里需要把环的模运算考虑进去。实际上因为环是闭合的距离应该用模 b 来计算。当距离为 1 时快指针追近 1 步后距离变为 0即相遇。不会跳过因为追近量恰好是 1而距离是整数。如果快指针每次走三步慢指针走一步追近量是 2那就有可能跳过。所以“快指针走两步”这个选择不是随便定的它保证了追近量为 1从而保证必然相遇且不会跳过。3.2 相遇时各指针走过的距离现在做定量分析。设头节点到环入口的距离为 a环入口到相遇点的距离为 x环的长度为 b。注意 x 是沿环前进方向从入口到相遇点的距离所以 0 ≤ x b。慢指针走过的总距离从头部走到入口是 a 步从入口走到相遇点是 x 步总共 a x 步。因为慢指针速度是 1所以它走的步数等于时间。快指针走过的总距离快指针速度是 2所以它走的步数是慢指针的两倍即 2(a x) 步。但快指针的路径可以这样描述它先走 a 步到入口然后可能在环内绕了若干整圈最后停在相遇点。设它在环内绕了 n 整圈n ≥ 1因为快指针先进环至少绕了一圈才可能被慢指针追上其实 n 可以是 0 吗如果 a 很小快指针可能还没绕完一圈慢指针就进环了但快指针在慢指针进环前已经在环内走了所以从快指针到达入口算起它走的距离是 2(ax) - a a 2x。这个距离等于 n*b x其中 n 是快指针在环内绕的整圈数。所以有2(a x) a n*b x化简得a x n*b即a n*b - x这个等式就是整个证明的核心。它告诉我们头节点到环入口的距离 a等于快指针在环内绕的整圈数乘以环长再减去从入口到相遇点的距离 x。换句话说a 等于 (n-1)*b (b - x)。而 b - x 正是从相遇点继续沿环前进到入口的距离。3.3 为什么二次追击能找到入口有了 a nb - x 这个等式二次追击的正确性就一目了然了。现在让一个指针从头部出发另一个指针从相遇点出发两者都每次走一步。从头出发的指针走 a 步到达入口。从相遇点出发的指针走 a 步会到哪里它从相遇点出发沿环前进走 a 步。因为 a nb - x而环长是 b所以走 n*b - x 步相当于走 (n-1)*b (b - x) 步。走 (n-1)*b 步是绕了 n-1 整圈回到相遇点再走 b - x 步就到达入口。所以从相遇点出发的指针走 a 步后也恰好到达入口。两者在入口相遇问题解决。这个证明的美妙之处在于它把“距离”和“圈数”通过模运算联系起来了。n 的具体值不重要重要的是 a 和 b - x 在模 b 意义下相等。这也是为什么二次追击不需要知道 n 是多少直接同速走就行。3.4 一个具体数值例子走一遍光看公式可能还是抽象我拿一组具体数字走一遍。假设 a 3b 5即环外有3个节点环有5个节点。链表结构是节点1→节点2→节点3→节点4→节点5→节点6→节点7→节点4环从节点4开始环是4→5→6→7→4环长4等等我设 b5那环应该有5个节点。重新设节点1→2→3→4→5→6→7→8→4环从节点4开始环是4→5→6→7→8→4环长5a3。慢指针从节点1出发快指针从节点1出发。时间线如下时间0慢在1快在1。时间1慢到2快到3。时间2慢到3快到5。时间3慢到4入口快到7。时间4慢到5快到4绕了一圈回到入口快从7走两步到47→8→4是的到4。时间5慢到6快到6快从4走两步到64→5→6。相遇相遇点是节点6。此时 a3x 是从入口节点4到相遇点节点6的距离沿环前进4→5→6所以 x2。b5。验证等式 a x n*b325n1。成立。现在二次追击一个指针从头节点1出发另一个从相遇点节点6出发都每次走一步。时间1头指针到2相遇点指针到7。时间2头指针到3相遇点指针到8。时间3头指针到4入口相遇点指针到48→4。相遇在入口节点4。完美。这个例子把整个过程具象化了你可以自己拿纸画一下比看十遍公式都管用。4. 代码实现与边界处理4.1 判断是否有环的代码先写最简单的版本只判断有没有环。用两个指针slow 和 fast初始都指向头节点。循环条件是 fast 和 fast.next 都不为空因为 fast 要走两步必须保证 fast.next 存在才能取 fast.next.next。def has_cycle(head): if head is None or head.next is None: return False slow head fast head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow fast: return True return False这段代码里循环条件fast is not None and fast.next is not None是关键。如果 fast 为空说明已经走到链表末尾无环如果 fast.next 为空说明 fast 在最后一个节点再走两步会越界也无环。两个条件缺一不可。4.2 找到环入口的完整代码在判断有环的基础上相遇后让一个指针回到头部然后两个指针同速前进再次相遇就是入口。def detect_cycle(head): if head is None or head.next is None: return None slow head fast head # 第一阶段找相遇点 while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow fast: break else: # 循环正常结束说明无环 return None # 第二阶段找入口 slow head while slow ! fast: slow slow.next fast fast.next return slow这里用了 Python 的while...else结构当循环因为条件不满足而结束时执行 else 分支返回 None当因为 break 结束时跳过 else 继续执行第二阶段。这个写法比较紧凑但如果你不熟悉while...else可以用一个标志变量代替可读性更好。4.3 边界情况逐个排查边界情况是这道题最容易翻车的地方。我列一下我遇到过的空链表head 为 None直接返回无环。单节点无环head.next 为 None直接返回无环。单节点自环head.next 指向自己。此时 slow 和 fast 初始都在 head第一次循环 slow 到 headfast 到 head因为 fast.next.next 就是 head相遇返回 head。正确。环从头部开始a0。此时慢指针一进环就可能在入口附近快指针可能已经在环内。证明依然成立a0 时等式变成 x nb即 x 是 b 的倍数但 x b所以 x0n0这里 n 的定义需要小心。如果 a0快指针和慢指针同时从入口出发快指针走两步慢指针走一步第一次快指针走两步到环内第二个节点慢指针走一步到环内第一个节点然后快指针继续追最终在某个点相遇。此时 a0等式 ax nb 变成 x n*b但 0 ≤ x b所以 x0n0。这意味着相遇点就是入口。二次追击时头指针和相遇点指针都在入口直接返回。代码里第二阶段 slowheadfast相遇点入口head循环条件 slow ! fast 不成立直接返回 head。正确。环很长尾巴很短比如 a1b100。快指针先进环慢指针进环时快指针可能已经绕了很多圈。证明依然成立n 会比较大但不影响结论。4.4 代码中的常见笔误写快慢指针时有几个笔误我见过太多次第一个是循环条件写成while fast and fast.next但在循环体内先移动了 slow 再移动 fast导致 fast 可能已经为空却还去取 fast.next。正确的顺序是先检查条件再移动。或者把移动放在条件检查之后但要注意 fast 移动两步前必须确保 fast.next 存在。第二个是第二阶段忘记把 slow 重置回头部直接拿相遇点的 slow 和 fast 继续走结果两个指针同速但起点相同永远不相遇除非入口就是相遇点。第三个是返回时返回了 slow 的值而不是节点本身。题目要的是入口节点不是节点的值。第四个是在第一阶段相遇后没有 break继续循环导致 slow 和 fast 再次分开。虽然有些写法不加 break 也能在下次相遇时退出但逻辑不清晰容易出错。5. 常见问题与排查技巧实录5.1 为什么快指针不能走三步或更多前面提过快指针走两步时追近量是 1保证不会跳过慢指针。如果快指针走三步追近量是 2。当两者距离为 1 时快指针走三步慢指针走一步快指针会从慢指针前方 1 步变成前方 3 步但环是闭合的距离要模 b。如果 b 是偶数距离 1 加 2 等于 3模 b 后可能变成 3 或 b-3不一定为 0所以可能跳过。具体来说当距离为 1 且 b 为偶数时走一步后距离变成 3再走一步变成 5永远碰不到 0因为每次加 2奇偶性不变。所以快指针走三步不保证相遇。走两步是保证相遇的最小速度差也是最优选择。5.2 相遇点一定是环内节点吗是的。因为慢指针进入环后才会被快指针追上而慢指针进入环后走的每一步都在环内所以相遇点必然在环内。如果链表无环快指针会先到空根本不会相遇。5.3 如果链表有环但快指针先到空怎么办这种情况不会发生。如果链表有环快指针永远不会到空因为环内没有空指针。快指针会在环内无限循环直到追上慢指针。所以只要链表有环循环一定会因为相遇而 break不会因为 fast 为空而退出。5.4 二次追击时两个指针速度必须相同吗是的。二次追击的原理是 a n*b - x即从头走 a 步和从相遇点走 a 步到达同一个位置。如果速度不同走的步数就不同等式不成立。所以必须同速每次走一步。5.5 常见问题速查表问题现象可能原因排查方法程序死循环链表有环但快慢指针没相遇检查快指针是否每次走两步慢指针是否每次走一步返回 None 但实际有环第一阶段循环条件写错提前退出检查fast and fast.next条件是否正确返回的入口不对第二阶段没重置 slow 到头节点确认slow head在第二阶段开始前执行单节点自环返回 None初始判断head.next is None误判单节点自环时 head.next 不是 None是 head 本身空链表报错没做空指针判断函数开头加if head is None判断5.6 几个我踩过的坑第一个坑是早期写代码时把快指针的初始化写成fast head.next想省一次循环。这在某些情况下能工作但证明过程会变而且边界情况容易出错。后来我统一用fast head逻辑最清晰。第二个坑是在面试时被问到“如果快指针走两步慢指针走一步但快指针先走慢指针后走会不会影响结果”。答案是会影响相遇点的位置但不会影响有环的判断和入口的正确性。因为证明里的时间线是同步的如果异步走相当于改变了初始相位但最终等式依然成立只是 n 的值可能不同。不过为了证明简洁建议同步走。第三个坑是忽略了 Python 中while...else的执行逻辑。如果循环体里有 breakelse 不执行如果循环条件不满足而自然结束else 执行。这个特性在找入口时很好用但如果不熟悉容易写出逻辑错误的代码。6. 从环形链表延伸出去的思考环形链表问题表面上是一道算法题但它背后的“快慢指针数学证明”模式在很多地方都能看到影子。比如在判断一个迭代函数是否会进入循环时可以用类似的方法检测在分析状态机是否有死循环时也可以用快慢指针的思想。甚至在某些去重和找重复数的题目里也能把数组下标当作指针构造出隐式的链表然后用环形链表的解法来解。我个人在实际操作中的体会是这道题最大的价值不是让你记住一个解法而是训练你把一个动态过程抽象成静态方程的能力。当你能够把“快指针走了多少步”“慢指针走了多少步”“它们在环内绕了几圈”这些量用等式联系起来你就掌握了分析这类问题的通用工具。下次遇到类似的追击问题、周期问题你也能自己推导出结论而不是去背答案。最后再分享一个小技巧如果你在面试时一时忘了证明过程可以先用具体数字试一遍比如设 a3, b5手动模拟一遍找到相遇点和入口然后反推等式。很多时候具体例子能帮你回忆起抽象公式。这个方法我在讲题时用过很多次比干想公式有效得多。
