很多同学在接触“快慢指针找环”这个经典问题时都是靠背代码过关的。第一阶段慢指针每次走一步快指针每次走两步如果两个指针相遇了说明链表有环第二阶段把某个指针重置到链表头再让两个指针一步一步走第二次相遇的位置就是环入口。代码两三行就写完了但真被问到“为什么要重置重置后为什么一定会相遇到入口”的时候很多人就卡住了。我自己在面试别人时这个问题问过很多次能完整推导出来的人确实不多。这篇文章准备专门把“重置快/慢指针”这个动作讲透同时把“找环”“找入口”“算环长”“找中间节点”“找倒数第k个节点”这几个容易混的场景放在一起辨析。如果你正在准备算法面试或者工作中要处理循环链表、环型依赖这类结构这篇应该能帮你少走不少弯路。1. 第一阶段判断有没有环这一步根本不涉及重置1.1 快慢指针的移动规则与基础代码先来看最基础的一段代码。这里的 head 是链表的头节点slow 和 fast 都从 head 出发def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这段代码里有两个细节值得停下来想一想。第一fast 为什么可以被当成普通节点来访问两次 next因为循环条件里已经保证了 fast 本身不为空、fast.next 也不为空所以 fast.next.next 不会因为 fast.next 为空而抛异常。第二如果链表没有环循环会在 fast 或者 fast.next 为空的时候退出此时返回 False如果链表有环循环永远不会因为 fast 走到末尾而退出唯一的退出方式就是 slow 和 fast 相遇然后返回 True。很多文章会把这一步称为“龟兔赛跑”兔子跑得快乌龟跑得慢如果跑道是环形的兔子迟早会从后面追上乌龟如果跑道是直的兔子会先跑到终点。这个比喻非常直观我也经常用但要注意它只能解释到“有环就一定会相遇”这一层还解释不了“相遇点在哪里”以及“怎么从相遇点找入口”这两个问题后面两节会把这些补上。提示这里我特意让 slow 和 fast 都从 head 出发。有些写法会让 fast 从 head.next 出发从“判断有没有环”的角度来说也能过但后面的入口推导会变得不那么直观所以本文统一用都从 head 出发的写法。1.2 为什么快指针每次走2步而不是3步或4步这是很多初学者会问的问题。为什么不选3步、4步其实核心只有一个词相对速度。快指针每次走2步、慢指针每次走1步那么每一轮过去快指针比慢指针多走1步。在环上只要两者之间有距离差这个距离差每轮就会稳定地缩小1不存在“跨过去”的情况所以最多走完一圈的长度快指针一定能追上慢指针。如果把快指针改成每次走3步相对速度就变成了2。这会有两个问题。第一追击距离每轮缩小2当这个距离是奇数而环长是偶数的时候快指针可能会从慢指针“身边”跨过去本来该追上的那一轮变成了超车于是需要再多绕一圈。第二从同余的角度看相对速度2和环周长如果不满足特定关系还会出现永远追不上的情况。举个最简单的例子环上只有两个节点快指针落后1步每一次相对位置都会因为加2而对环长取模变成原地踏步两个指针之间的距离永远不变。所以经典算法里选“快2慢1”不是随便选的而是为了把相对速度控制在1让数学性质最干净。另一个被问得比较多的问题是为什么不能让快指针每次走1步、慢指针不动因为如果慢指针停在一个链表上的非环节点快指针永远都跑不到它那里即使慢指针停在环上也要求它恰好停在被快指针经过的那个节点这种写法没有任何通用性。因此慢指针必须具备“自己也往前走”的能力快指针才能通过相对速度1去追它。1.3 无环与有环两条完全不同的退出路径这里要特别说明一下无环和成环时循环的退出差异因为这直接影响后面“是否该重置”的判断。无环链表是单行道。fast 每轮走两步它会先于 slow 到达链表的末尾。当 fast 指向 None、或者 fast.next 指向 None 时while 条件不成立循环自然结束。注意如果链表只有一个节点初始 fast 和 slow 都等于 headfast.next 是 None循环直接就退出了更不会发生一次移动。有环链表上不存在 None因为环里的节点永远有下一跳。这时候 while 判空条件形同虚设循环只可能因为 break 或者 return 退出。所以在判断是否有环的代码里必须把“slow fast”放在循环体内判断并且一旦满足就立刻返回 True。如果写成下面的错误版本while fast and fast.next: slow slow.next fast fast.next.next return slow fast在有环链表上会怎样代码根本走不到 return 那一行因为它在环里永远不会退出直接变成死循环。这种错误在初学者代码里出现频率很高值得留意。2. 重置快/慢指针的核心逻辑为什么重置后能在入口相遇2.1 重置操作与两种等价写法第一阶段只能告诉我们“有环”但环入口在哪里并不知道。要找到入口就需要第二步重置指针。最经典的写法是重置慢指针到链表头快指针留在相遇点不再“赛跑”然后两个指针都改成每次走1步直到两者再次相等那个位置就是环入口。def detect_cycle_start(head): slow head fast head has_cycle False while fast and fast.next: slow slow.next fast fast.next.next if slow fast: has_cycle True break if not has_cycle: return None slow head # 重置慢指针到链表头 while slow ! fast: # 两个指针都每次走1步 slow slow.next fast fast.next return slow细心的读者会发现这里重置的是 slow。如果把第二段改成把 fast 重置到链表头、slow 留在相遇点效果完全一样fast head while slow ! fast: slow slow.next fast fast.next return slow为什么两种写法都能得到入口因为第二阶段真正要求的不是一个“固定的指针”回到链表头而是“两个指针中有一个回到链表头另一个保持在相遇点”。至于具体是哪个指针回到头部不影响任何推导。很多题解里一会儿重置慢指针、一会儿重置快指针把初学者搞晕了其实它们只是同一件事的两种写法。核心点是第二阶段的起点是一头一相遇点速度和步长都是1。注意第二阶段绝对不能继续保持“快2慢1”的速度。原因很简单快指针如果保持每次走2步它的追击逻辑又会启动两个人不一定在入口处相遇甚至可能再次错过和追赶把问题复杂化。第二阶段追求的是“两个步长为1的指针从两个固定起点出发在环入口精确会合”。2.2 数学推导相遇点与入口的距离关系要理解“为什么重置后能在入口相遇”需要一点简单的代数。定义三个量L链表头到环入口需要经过的节点数也就是从头节点走 L 步到达入口节点x环入口到第一阶段相遇点需要经过的节点数也就是从入口节点走 x 步到达相遇点C环的周长环上的节点总数。慢指针从链表头出发在相遇时总共走了 L x 步。为什么慢指针只走不到一圈因为当慢指针进入环时快指针已经至少领先它一步慢指针在环上还没走完一圈就会被追上这个结论可以直接用。快指针从链表头出发在相遇时总共走了 L x k*C 步其中 k 是快指针相对慢指针多绕的整圈数k 至少为1。又因为快指针速度是慢指针的两倍所以L x k*C 2 * (L x)化简得到L k*C - x这个式子就是整道题的核心。它说的是链表头到环入口的距离 L等于若干倍环周长减去“入口到相遇点”的距离 x。换句话说L (k - 1)*C (C - x)其中 C - x 是从相遇点继续往前走到入口的距离。于是如果一个指针站在链表头另一个指针站在相遇点两人都每次走1步走 L 步后链表头的指针到了入口相遇点的指针往前走 L 步相当于先走 C - x 到入口再整圈整圈地绕 (k - 1) 圈最终也停在入口。两者必然在入口处相遇。这就是第二阶段能精确找到入口的根本原因。这里有一个容易想不通的细节快指针在相遇时到底多绕了多少圈k 取几其实不重要因为等式两边已经把“圈数”消掉了。不管 k 是1、2还是更大的数L 和 C - x 之间始终存在这种“差一个环长整数倍”的关系所以重置后走 L 步的结论对所有 k 都成立。2.3 用真实例子跟踪一遍指针只看公式可能有点抽象我们来手动跑一个链表。构造一个带环链表1 - 2 - 3 - 4 - 5 - 6 - 3。它的入口是节点3L 等于2从节点1走两步到节点3环长 C 等于43 - 4 - 5 - 6 - 3。第一阶段从 slow fast 节点1开始每一轮两个指针的移动情况如下轮次slow位置fast位置初始11第1轮23第2轮35第3轮43第4轮55第4轮结束slow 和 fast 在节点5相遇。入口是节点3从入口到相遇点需要走2步3 - 4 - 5所以 x 2。C - x 4 - 2 2正好等于 L。现在进入第二阶段把 slow 重置到节点1fast 留在节点5。轮次slow位置fast位置初始15第1轮26第2轮33第2轮结束时两者在节点3相遇也就是环入口。直觉上看就是“从链表头走 L 步”和“从相遇点走 L 步等效于 C - x”刚好在入口处碰头。这个例子非常有代表性因为 L 恰好等于 C - x更容易看出对称性。换个 L 不等于 C - x 的例子结果也一样只是多绕几圈再碰头。2.4 第二阶段最容易犯的错误忘记把速度改成1步说句实话我在代码评审里见过最多的错误不是第一阶段写不对而是第二阶段把重置做对了速度却忘了改。比如有人写了slow head while slow ! fast: slow slow.next fast fast.next.next # 错第二阶段还在用2倍速这个版本在部分链表上可能碰巧能算对但大概率会在入口处错过或者陷入死循环。因为此时 fast 仍然保持“每轮追上一步”的追击状态它的行为不再满足上面那条 L k*C - x 的推导前提。第二阶段的每一步都必须把两个指针放在同一个速度上这一点值得在代码旁边写一行注释提醒自己这里不是龟兔赛跑了现在是两只乌龟在走。3. 场景辨析哪些要重置哪些不要3.1 仅判断是否存在环如果需求只是“这链表有没有环”第一阶段跑完就结束了完全不需要第二阶段。很多人会习惯性地把“探测环”和“找入口”写进同一个函数这是没必要的。判断有环的代码只需要返回布尔值在 slow fast 成立时返回 True循环正常退出时返回 False干净利落。这个场景是最基础的送分题不需要引入重置逻辑。3.2 定位环入口节点定位入口是“必须重置”的典型场景。这时候不仅要返回“有环”还要返回一个具体的节点引用。重置以后两个指针第二次相遇的节点就是入口。比如做循环引用分析、修复污染链表、或者要在入口处打断环都需要这个返回值。这个场景也是本文标题里“重置”一词最直接的落点。3.3 计算环的长度计算环长有两种做法都不需要重置到链表头。第一种做法是先找到入口然后从入口节点出发每次走一步用计数器记录走了多少步重新回到入口这个步数就是环长 C。第二种做法是在第一阶段相遇后让其中一个指针保持在相遇点另一个继续走等它再次回到相遇点时走的步数也正好是一个环长。这里有一个很有意思的小点从环上任意一个节点出发走回同一个节点走的步数都是一样的都等于环长。所以“计算环长度”这个场景关心的是 C而不是入口位置。你完全可以在第一阶段相遇点直接开始计数省去第二阶段的入口推导。但如果你的需求既要入口又要长度那就先做第二阶段拿入口再数一圈拿长度两条路径是串行关系。3.4 寻找链表中间节点快慢指针的经典应用之一是找链表中间节点。同样是 slow 每次1步、fast 每次2步但判断的是“快指针是否到达尾部”。当链表长度是奇数时fast 会落在最后一个节点上slow 正好落在中间节点当链表长度是偶数时fast 会落在 None 上slow 落在两个中间节点中的第二个。这个场景和找环最明显的区别是不需要第二阶段不需要重置连环的存在都不关心。如果链表里有环还去找中间节点逻辑会完全跑偏所以使用前得先确认链表是无环的。这个场景最有价值的衍生应用是回文链表判断。先用快慢指针找到中间节点再把后半段反转最后逐节点对比。它和“找环”虽然都叫快慢指针但一个服务于对称性校验一个服务于环结构分析理念完全不同。3.5 寻找倒数第k个节点“倒数第k个节点”也会用双指针但这里的双指针初始并不是“速度差”而是“偏移差”。具体做法是让 fast 先走 k 步然后 fast 和 slow 一起每次走1步。当 fast 走到链表末尾 None 时slow 正好指向倒数第k个节点。这个场景经常被误称为快慢指针但严格来说它的两个指针速度相同只是出发位置不同。它和“找环”的辨析点在于如果题目里说“重置指针”请你先确认这是“相遇后重置”还是“出发前让一个指针先走k步”。后者跟环入口没有一点关系只是因为某种原因也叫“双指针技巧”。其实原理很简单先走 k 步相当于让两个指针对齐一个长度差剩下就变成“找链表末尾的第k个位置”的线性问题。3.6 两个链表找交点的“换路”不是快慢指针还有一个更容易混淆的场景是“两个链表找交点”。这类题的常见做法是两个指针分别从两个链表头出发速度都是1步当某个指针走到链表尾部时跳到另一个链表的头部继续走。如果两个链表相交它们会在交点相遇如果不相交它们会同时走到尾部。这个技巧看代码很像“重置指针”指针 A 走到头后重置到链表 B 的头指针 B 走到头后重置到链表 A 的头。但它和“找环第二步”的重置完全是两码事。找环第二步的重置是为了让两个指针在环入口会合依据的是相遇点与入口的距离关系而找交点的“换路”是为了构造长度对齐让两个指针同时走到交点。把这两者放在一起看会发现“重置”这个词在不同上下文里含义差异很大。理解到这一层才算真正把双指针场景辨析清楚了。3.7 场景速查表我把上面几个场景整理成一张表方便你复习时一眼定位。场景双指针速度是否需要“相遇后重置”主要计算目标判断链表是否有环快2慢1不需要是否存在环定位环入口第一阶段快2慢1第二阶段1:1必须入口节点计算环长度第一阶段快2慢1之后1:1数圈不需要环周长 C找链表中间节点快2慢1不需要中间节点找倒数第k个节点1:1fast先走k步不需要出发前偏移倒数第k节点两个链表找交点1:1走到底换路不需要走到头换路交点节点4. 边界条件与源码级陷阱4.1 判空条件怎么写才安全第一阶段循环条件写成 while fast and fast.next是最稳妥的写法。它同时保证了 fast 本身不为空以及 fast.next 不为空这样 fast.next.next 才安全。如果写成 while fast.next那么当快指针指向最后一个节点时循环还能进入但 fast.next.next 直接抛异常如果写成 while fast那么当 fast 指向 None 时循环虽然不进入但在循环内 fast.next 可能抛异常。这里有一点容易被忽略有环链表上的循环并不会因为判空条件而退出所以判空条件只对无环情况有效。对带环链表来说真正的出口必然是 slow fast 分支里的 return 或 break。两个机制缺一不可。4.2 特殊链表形态逐个过我建议大家在写完代码后至少用下面几种输入自测一遍。第一种空链表 head 为 None第一阶段循环直接跳过返回 None正确。第二种单节点无环链表 head.next 为 None也直接跳过循环返回 None正确。第三种单节点成环 head.next head第一阶段第一轮 slow 和 fast 都到 head两者相遇重置 slow 回到 head 后第二阶段第一次判断就相等直接返回 head入口就是它自己正确。第四种双节点成环 1 - 2 - 1手动跑一遍也能验证结果。第五种入口就在链表头的环比如 1 - 2 - 3 - 1此时 L 0第一阶段会在入口节点相遇第二阶段把 slow 重置到 head 后第一轮就是 slow fast直接返回 head。这五种形态虽然简单但能暴露出大部分实现问题。提示如果本地没有测试框架可以在链表节点类里加一个“节点ID”字段调试时打印每一步指针所在节点的ID能肉眼看出相遇位置和入口位置是否符合预期。4.3 常见错误实现诊断我把平时看到的错误实现归纳成四类你可以对照检查自己有没有踩过。第一类fast 从 head.next 出发。这种写法判断是否有环没问题但第二阶段如果仍然假设“从头走 L 步到入口”推导需要微调。不是不能用但初学时建议统一从 head 出发减少心智负担。第二类第二阶段忘记把两个指针都改成1步。前面专门讲过这是重灾区。症状是代码在部分用例上结果正确在部分用例上死循环或者返回错误节点。第三类无环链表上调用第二阶段。如果直接调用 detect_cycle_start而链表没有环第一阶段结束后 fast 可能已经为 None此时不能进入第二阶段。所以第二阶段之前必须判断是否有环没环直接返回 None。第四类把节点值和节点引用混为一谈。链表中可能存在重复值判断相遇时比较的是“是否是同一个节点对象”而不是“节点值是否相等”。拿值相等来判环会在有重复值的链表上得到错误结论。4.4 一行日志快速定位问题排查这类问题时我习惯在循环里打印指针位置。比如在代码里给节点加一个 index 字段然后打印 slow.index 和 fast.index。如果两个 index 序列出现循环但不相等说明代码路径里可能有逻辑错误如果循环很久都很正常那大概率是第二阶段速度没有改回来。打印日志虽然土但比盯着代码空想要高效得多。等确认逻辑正确后再把日志删掉。5. 快慢指针在真实项目中的应用与选型参考5.1 环型结构检测快慢指针最直接的业务映射是“检测循环结构”。比如一些脚本引擎或规则引擎中节点之间存在引用关系如果配置不小心出现了循环引用遍历时会进入死循环。此时可以用快慢指针在遍历链路时检测环。不过要注意真实的依赖关系往往是多分支的图结构而不是简单的链表。快慢指针更适合“单链线性追踪”场景一旦涉及多入度、多出度的图更通用的是拓扑排序或染色法。链表的快慢指针是理解“环检测”的最小模型但它不等于图上的环检测。5.2 环形缓冲与约瑟夫问题环形缓冲区、约瑟夫环这类问题和“环”天然相关。约瑟夫问题中人们绕着圈报数报到的节点出列本质上就是在环形链表上做删除操作。这时候双指针思路可以在快速跳过或定位时辅助但它和“检测环”已经是完全不同的任务。快慢指针的价值在于它用一个 O(1) 空间的办法完成环结构分析而不是靠额外哈希表记录访问过的节点。5.3 为什么多数场景用HashSet就够了很多工程场景下判断链表是否有环其实用哈希表更省事遍历节点把每个节点引用放进集合里如果发现某个节点已经出现过说明有环。这个做法直观、代码简单、容易调试代价是额外空间 O(n)。而快慢指针的独特价值是空间复杂度只有 O(1)不需要任何额外容器。在内存受限的系统、或者面试考察“无额外空间”的约束下快慢指针是更合适的选择。如果内存不紧张两者都可以但你需要理解为什么面试官会问“你用 HashSet 做的话空间是 O(n)能不能优化到 O(1)”这一层。5.4 面试时的表达顺序建议最后给要面试的朋友一点建议。当被问到“如何找到链表环入口”时千万不要只背代码。一个比较推荐的表达顺序是先说明第一阶段如何判断有环再说明为什么快指针选2步而不是3步相对速度1然后引入 L、x、C 三个量推导 L k*C - x最后解释重置指针后两个指针为什么在入口相遇。这样一套讲下来面试官会觉得你是真的理解而不是背题。如果直接被要求写代码可以在写完之后口头把边界条件空链表、单节点、无环、入口在头节点逐个过一遍这比沉默着写完效果要好得多。我实际写过很多次这个算法也帮不少同学改过相关代码。说实话第一次学到第二阶段的时候我也觉得很神奇凭什么一个指针回到头另一个留在相遇点两个人都走一步最后就正好在入口碰面直到自己拿纸笔画了链表又跑了几个例子才真正把那个等式印在脑子里。如果你现在也觉得这步很玄建议你先别急着背代码拿个链表画一画把 L、x、C 标出来自己算一次比看十遍解析都管用。最后分享一个小技巧验证环入口算法时构造一个“入口在链表头”的环和一个“入口在中段”的环环长一奇一偶把两种情况都测通了代码基本就稳了。
很多同学在接触“快慢指针找环”这个经典问题时都是靠背代码过关的。第一阶段慢指针每次走一步快指针每次走两步如果两个指针相遇了说明链表有环第二阶段把某个指针重置到链表头再让两个指针一步一步走第二次相遇的位置就是环入口。代码两三行就写完了但真被问到“为什么要重置重置后为什么一定会相遇到入口”的时候很多人就卡住了。我自己在面试别人时这个问题问过很多次能完整推导出来的人确实不多。这篇文章准备专门把“重置快/慢指针”这个动作讲透同时把“找环”“找入口”“算环长”“找中间节点”“找倒数第k个节点”这几个容易混的场景放在一起辨析。如果你正在准备算法面试或者工作中要处理循环链表、环型依赖这类结构这篇应该能帮你少走不少弯路。1. 第一阶段判断有没有环这一步根本不涉及重置1.1 快慢指针的移动规则与基础代码先来看最基础的一段代码。这里的 head 是链表的头节点slow 和 fast 都从 head 出发def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这段代码里有两个细节值得停下来想一想。第一fast 为什么可以被当成普通节点来访问两次 next因为循环条件里已经保证了 fast 本身不为空、fast.next 也不为空所以 fast.next.next 不会因为 fast.next 为空而抛异常。第二如果链表没有环循环会在 fast 或者 fast.next 为空的时候退出此时返回 False如果链表有环循环永远不会因为 fast 走到末尾而退出唯一的退出方式就是 slow 和 fast 相遇然后返回 True。很多文章会把这一步称为“龟兔赛跑”兔子跑得快乌龟跑得慢如果跑道是环形的兔子迟早会从后面追上乌龟如果跑道是直的兔子会先跑到终点。这个比喻非常直观我也经常用但要注意它只能解释到“有环就一定会相遇”这一层还解释不了“相遇点在哪里”以及“怎么从相遇点找入口”这两个问题后面两节会把这些补上。提示这里我特意让 slow 和 fast 都从 head 出发。有些写法会让 fast 从 head.next 出发从“判断有没有环”的角度来说也能过但后面的入口推导会变得不那么直观所以本文统一用都从 head 出发的写法。1.2 为什么快指针每次走2步而不是3步或4步这是很多初学者会问的问题。为什么不选3步、4步其实核心只有一个词相对速度。快指针每次走2步、慢指针每次走1步那么每一轮过去快指针比慢指针多走1步。在环上只要两者之间有距离差这个距离差每轮就会稳定地缩小1不存在“跨过去”的情况所以最多走完一圈的长度快指针一定能追上慢指针。如果把快指针改成每次走3步相对速度就变成了2。这会有两个问题。第一追击距离每轮缩小2当这个距离是奇数而环长是偶数的时候快指针可能会从慢指针“身边”跨过去本来该追上的那一轮变成了超车于是需要再多绕一圈。第二从同余的角度看相对速度2和环周长如果不满足特定关系还会出现永远追不上的情况。举个最简单的例子环上只有两个节点快指针落后1步每一次相对位置都会因为加2而对环长取模变成原地踏步两个指针之间的距离永远不变。所以经典算法里选“快2慢1”不是随便选的而是为了把相对速度控制在1让数学性质最干净。另一个被问得比较多的问题是为什么不能让快指针每次走1步、慢指针不动因为如果慢指针停在一个链表上的非环节点快指针永远都跑不到它那里即使慢指针停在环上也要求它恰好停在被快指针经过的那个节点这种写法没有任何通用性。因此慢指针必须具备“自己也往前走”的能力快指针才能通过相对速度1去追它。1.3 无环与有环两条完全不同的退出路径这里要特别说明一下无环和成环时循环的退出差异因为这直接影响后面“是否该重置”的判断。无环链表是单行道。fast 每轮走两步它会先于 slow 到达链表的末尾。当 fast 指向 None、或者 fast.next 指向 None 时while 条件不成立循环自然结束。注意如果链表只有一个节点初始 fast 和 slow 都等于 headfast.next 是 None循环直接就退出了更不会发生一次移动。有环链表上不存在 None因为环里的节点永远有下一跳。这时候 while 判空条件形同虚设循环只可能因为 break 或者 return 退出。所以在判断是否有环的代码里必须把“slow fast”放在循环体内判断并且一旦满足就立刻返回 True。如果写成下面的错误版本while fast and fast.next: slow slow.next fast fast.next.next return slow fast在有环链表上会怎样代码根本走不到 return 那一行因为它在环里永远不会退出直接变成死循环。这种错误在初学者代码里出现频率很高值得留意。2. 重置快/慢指针的核心逻辑为什么重置后能在入口相遇2.1 重置操作与两种等价写法第一阶段只能告诉我们“有环”但环入口在哪里并不知道。要找到入口就需要第二步重置指针。最经典的写法是重置慢指针到链表头快指针留在相遇点不再“赛跑”然后两个指针都改成每次走1步直到两者再次相等那个位置就是环入口。def detect_cycle_start(head): slow head fast head has_cycle False while fast and fast.next: slow slow.next fast fast.next.next if slow fast: has_cycle True break if not has_cycle: return None slow head # 重置慢指针到链表头 while slow ! fast: # 两个指针都每次走1步 slow slow.next fast fast.next return slow细心的读者会发现这里重置的是 slow。如果把第二段改成把 fast 重置到链表头、slow 留在相遇点效果完全一样fast head while slow ! fast: slow slow.next fast fast.next return slow为什么两种写法都能得到入口因为第二阶段真正要求的不是一个“固定的指针”回到链表头而是“两个指针中有一个回到链表头另一个保持在相遇点”。至于具体是哪个指针回到头部不影响任何推导。很多题解里一会儿重置慢指针、一会儿重置快指针把初学者搞晕了其实它们只是同一件事的两种写法。核心点是第二阶段的起点是一头一相遇点速度和步长都是1。注意第二阶段绝对不能继续保持“快2慢1”的速度。原因很简单快指针如果保持每次走2步它的追击逻辑又会启动两个人不一定在入口处相遇甚至可能再次错过和追赶把问题复杂化。第二阶段追求的是“两个步长为1的指针从两个固定起点出发在环入口精确会合”。2.2 数学推导相遇点与入口的距离关系要理解“为什么重置后能在入口相遇”需要一点简单的代数。定义三个量L链表头到环入口需要经过的节点数也就是从头节点走 L 步到达入口节点x环入口到第一阶段相遇点需要经过的节点数也就是从入口节点走 x 步到达相遇点C环的周长环上的节点总数。慢指针从链表头出发在相遇时总共走了 L x 步。为什么慢指针只走不到一圈因为当慢指针进入环时快指针已经至少领先它一步慢指针在环上还没走完一圈就会被追上这个结论可以直接用。快指针从链表头出发在相遇时总共走了 L x k*C 步其中 k 是快指针相对慢指针多绕的整圈数k 至少为1。又因为快指针速度是慢指针的两倍所以L x k*C 2 * (L x)化简得到L k*C - x这个式子就是整道题的核心。它说的是链表头到环入口的距离 L等于若干倍环周长减去“入口到相遇点”的距离 x。换句话说L (k - 1)*C (C - x)其中 C - x 是从相遇点继续往前走到入口的距离。于是如果一个指针站在链表头另一个指针站在相遇点两人都每次走1步走 L 步后链表头的指针到了入口相遇点的指针往前走 L 步相当于先走 C - x 到入口再整圈整圈地绕 (k - 1) 圈最终也停在入口。两者必然在入口处相遇。这就是第二阶段能精确找到入口的根本原因。这里有一个容易想不通的细节快指针在相遇时到底多绕了多少圈k 取几其实不重要因为等式两边已经把“圈数”消掉了。不管 k 是1、2还是更大的数L 和 C - x 之间始终存在这种“差一个环长整数倍”的关系所以重置后走 L 步的结论对所有 k 都成立。2.3 用真实例子跟踪一遍指针只看公式可能有点抽象我们来手动跑一个链表。构造一个带环链表1 - 2 - 3 - 4 - 5 - 6 - 3。它的入口是节点3L 等于2从节点1走两步到节点3环长 C 等于43 - 4 - 5 - 6 - 3。第一阶段从 slow fast 节点1开始每一轮两个指针的移动情况如下轮次slow位置fast位置初始11第1轮23第2轮35第3轮43第4轮55第4轮结束slow 和 fast 在节点5相遇。入口是节点3从入口到相遇点需要走2步3 - 4 - 5所以 x 2。C - x 4 - 2 2正好等于 L。现在进入第二阶段把 slow 重置到节点1fast 留在节点5。轮次slow位置fast位置初始15第1轮26第2轮33第2轮结束时两者在节点3相遇也就是环入口。直觉上看就是“从链表头走 L 步”和“从相遇点走 L 步等效于 C - x”刚好在入口处碰头。这个例子非常有代表性因为 L 恰好等于 C - x更容易看出对称性。换个 L 不等于 C - x 的例子结果也一样只是多绕几圈再碰头。2.4 第二阶段最容易犯的错误忘记把速度改成1步说句实话我在代码评审里见过最多的错误不是第一阶段写不对而是第二阶段把重置做对了速度却忘了改。比如有人写了slow head while slow ! fast: slow slow.next fast fast.next.next # 错第二阶段还在用2倍速这个版本在部分链表上可能碰巧能算对但大概率会在入口处错过或者陷入死循环。因为此时 fast 仍然保持“每轮追上一步”的追击状态它的行为不再满足上面那条 L k*C - x 的推导前提。第二阶段的每一步都必须把两个指针放在同一个速度上这一点值得在代码旁边写一行注释提醒自己这里不是龟兔赛跑了现在是两只乌龟在走。3. 场景辨析哪些要重置哪些不要3.1 仅判断是否存在环如果需求只是“这链表有没有环”第一阶段跑完就结束了完全不需要第二阶段。很多人会习惯性地把“探测环”和“找入口”写进同一个函数这是没必要的。判断有环的代码只需要返回布尔值在 slow fast 成立时返回 True循环正常退出时返回 False干净利落。这个场景是最基础的送分题不需要引入重置逻辑。3.2 定位环入口节点定位入口是“必须重置”的典型场景。这时候不仅要返回“有环”还要返回一个具体的节点引用。重置以后两个指针第二次相遇的节点就是入口。比如做循环引用分析、修复污染链表、或者要在入口处打断环都需要这个返回值。这个场景也是本文标题里“重置”一词最直接的落点。3.3 计算环的长度计算环长有两种做法都不需要重置到链表头。第一种做法是先找到入口然后从入口节点出发每次走一步用计数器记录走了多少步重新回到入口这个步数就是环长 C。第二种做法是在第一阶段相遇后让其中一个指针保持在相遇点另一个继续走等它再次回到相遇点时走的步数也正好是一个环长。这里有一个很有意思的小点从环上任意一个节点出发走回同一个节点走的步数都是一样的都等于环长。所以“计算环长度”这个场景关心的是 C而不是入口位置。你完全可以在第一阶段相遇点直接开始计数省去第二阶段的入口推导。但如果你的需求既要入口又要长度那就先做第二阶段拿入口再数一圈拿长度两条路径是串行关系。3.4 寻找链表中间节点快慢指针的经典应用之一是找链表中间节点。同样是 slow 每次1步、fast 每次2步但判断的是“快指针是否到达尾部”。当链表长度是奇数时fast 会落在最后一个节点上slow 正好落在中间节点当链表长度是偶数时fast 会落在 None 上slow 落在两个中间节点中的第二个。这个场景和找环最明显的区别是不需要第二阶段不需要重置连环的存在都不关心。如果链表里有环还去找中间节点逻辑会完全跑偏所以使用前得先确认链表是无环的。这个场景最有价值的衍生应用是回文链表判断。先用快慢指针找到中间节点再把后半段反转最后逐节点对比。它和“找环”虽然都叫快慢指针但一个服务于对称性校验一个服务于环结构分析理念完全不同。3.5 寻找倒数第k个节点“倒数第k个节点”也会用双指针但这里的双指针初始并不是“速度差”而是“偏移差”。具体做法是让 fast 先走 k 步然后 fast 和 slow 一起每次走1步。当 fast 走到链表末尾 None 时slow 正好指向倒数第k个节点。这个场景经常被误称为快慢指针但严格来说它的两个指针速度相同只是出发位置不同。它和“找环”的辨析点在于如果题目里说“重置指针”请你先确认这是“相遇后重置”还是“出发前让一个指针先走k步”。后者跟环入口没有一点关系只是因为某种原因也叫“双指针技巧”。其实原理很简单先走 k 步相当于让两个指针对齐一个长度差剩下就变成“找链表末尾的第k个位置”的线性问题。3.6 两个链表找交点的“换路”不是快慢指针还有一个更容易混淆的场景是“两个链表找交点”。这类题的常见做法是两个指针分别从两个链表头出发速度都是1步当某个指针走到链表尾部时跳到另一个链表的头部继续走。如果两个链表相交它们会在交点相遇如果不相交它们会同时走到尾部。这个技巧看代码很像“重置指针”指针 A 走到头后重置到链表 B 的头指针 B 走到头后重置到链表 A 的头。但它和“找环第二步”的重置完全是两码事。找环第二步的重置是为了让两个指针在环入口会合依据的是相遇点与入口的距离关系而找交点的“换路”是为了构造长度对齐让两个指针同时走到交点。把这两者放在一起看会发现“重置”这个词在不同上下文里含义差异很大。理解到这一层才算真正把双指针场景辨析清楚了。3.7 场景速查表我把上面几个场景整理成一张表方便你复习时一眼定位。场景双指针速度是否需要“相遇后重置”主要计算目标判断链表是否有环快2慢1不需要是否存在环定位环入口第一阶段快2慢1第二阶段1:1必须入口节点计算环长度第一阶段快2慢1之后1:1数圈不需要环周长 C找链表中间节点快2慢1不需要中间节点找倒数第k个节点1:1fast先走k步不需要出发前偏移倒数第k节点两个链表找交点1:1走到底换路不需要走到头换路交点节点4. 边界条件与源码级陷阱4.1 判空条件怎么写才安全第一阶段循环条件写成 while fast and fast.next是最稳妥的写法。它同时保证了 fast 本身不为空以及 fast.next 不为空这样 fast.next.next 才安全。如果写成 while fast.next那么当快指针指向最后一个节点时循环还能进入但 fast.next.next 直接抛异常如果写成 while fast那么当 fast 指向 None 时循环虽然不进入但在循环内 fast.next 可能抛异常。这里有一点容易被忽略有环链表上的循环并不会因为判空条件而退出所以判空条件只对无环情况有效。对带环链表来说真正的出口必然是 slow fast 分支里的 return 或 break。两个机制缺一不可。4.2 特殊链表形态逐个过我建议大家在写完代码后至少用下面几种输入自测一遍。第一种空链表 head 为 None第一阶段循环直接跳过返回 None正确。第二种单节点无环链表 head.next 为 None也直接跳过循环返回 None正确。第三种单节点成环 head.next head第一阶段第一轮 slow 和 fast 都到 head两者相遇重置 slow 回到 head 后第二阶段第一次判断就相等直接返回 head入口就是它自己正确。第四种双节点成环 1 - 2 - 1手动跑一遍也能验证结果。第五种入口就在链表头的环比如 1 - 2 - 3 - 1此时 L 0第一阶段会在入口节点相遇第二阶段把 slow 重置到 head 后第一轮就是 slow fast直接返回 head。这五种形态虽然简单但能暴露出大部分实现问题。提示如果本地没有测试框架可以在链表节点类里加一个“节点ID”字段调试时打印每一步指针所在节点的ID能肉眼看出相遇位置和入口位置是否符合预期。4.3 常见错误实现诊断我把平时看到的错误实现归纳成四类你可以对照检查自己有没有踩过。第一类fast 从 head.next 出发。这种写法判断是否有环没问题但第二阶段如果仍然假设“从头走 L 步到入口”推导需要微调。不是不能用但初学时建议统一从 head 出发减少心智负担。第二类第二阶段忘记把两个指针都改成1步。前面专门讲过这是重灾区。症状是代码在部分用例上结果正确在部分用例上死循环或者返回错误节点。第三类无环链表上调用第二阶段。如果直接调用 detect_cycle_start而链表没有环第一阶段结束后 fast 可能已经为 None此时不能进入第二阶段。所以第二阶段之前必须判断是否有环没环直接返回 None。第四类把节点值和节点引用混为一谈。链表中可能存在重复值判断相遇时比较的是“是否是同一个节点对象”而不是“节点值是否相等”。拿值相等来判环会在有重复值的链表上得到错误结论。4.4 一行日志快速定位问题排查这类问题时我习惯在循环里打印指针位置。比如在代码里给节点加一个 index 字段然后打印 slow.index 和 fast.index。如果两个 index 序列出现循环但不相等说明代码路径里可能有逻辑错误如果循环很久都很正常那大概率是第二阶段速度没有改回来。打印日志虽然土但比盯着代码空想要高效得多。等确认逻辑正确后再把日志删掉。5. 快慢指针在真实项目中的应用与选型参考5.1 环型结构检测快慢指针最直接的业务映射是“检测循环结构”。比如一些脚本引擎或规则引擎中节点之间存在引用关系如果配置不小心出现了循环引用遍历时会进入死循环。此时可以用快慢指针在遍历链路时检测环。不过要注意真实的依赖关系往往是多分支的图结构而不是简单的链表。快慢指针更适合“单链线性追踪”场景一旦涉及多入度、多出度的图更通用的是拓扑排序或染色法。链表的快慢指针是理解“环检测”的最小模型但它不等于图上的环检测。5.2 环形缓冲与约瑟夫问题环形缓冲区、约瑟夫环这类问题和“环”天然相关。约瑟夫问题中人们绕着圈报数报到的节点出列本质上就是在环形链表上做删除操作。这时候双指针思路可以在快速跳过或定位时辅助但它和“检测环”已经是完全不同的任务。快慢指针的价值在于它用一个 O(1) 空间的办法完成环结构分析而不是靠额外哈希表记录访问过的节点。5.3 为什么多数场景用HashSet就够了很多工程场景下判断链表是否有环其实用哈希表更省事遍历节点把每个节点引用放进集合里如果发现某个节点已经出现过说明有环。这个做法直观、代码简单、容易调试代价是额外空间 O(n)。而快慢指针的独特价值是空间复杂度只有 O(1)不需要任何额外容器。在内存受限的系统、或者面试考察“无额外空间”的约束下快慢指针是更合适的选择。如果内存不紧张两者都可以但你需要理解为什么面试官会问“你用 HashSet 做的话空间是 O(n)能不能优化到 O(1)”这一层。5.4 面试时的表达顺序建议最后给要面试的朋友一点建议。当被问到“如何找到链表环入口”时千万不要只背代码。一个比较推荐的表达顺序是先说明第一阶段如何判断有环再说明为什么快指针选2步而不是3步相对速度1然后引入 L、x、C 三个量推导 L k*C - x最后解释重置指针后两个指针为什么在入口相遇。这样一套讲下来面试官会觉得你是真的理解而不是背题。如果直接被要求写代码可以在写完之后口头把边界条件空链表、单节点、无环、入口在头节点逐个过一遍这比沉默着写完效果要好得多。我实际写过很多次这个算法也帮不少同学改过相关代码。说实话第一次学到第二阶段的时候我也觉得很神奇凭什么一个指针回到头另一个留在相遇点两个人都走一步最后就正好在入口碰面直到自己拿纸笔画了链表又跑了几个例子才真正把那个等式印在脑子里。如果你现在也觉得这步很玄建议你先别急着背代码拿个链表画一画把 L、x、C 标出来自己算一次比看十遍解析都管用。最后分享一个小技巧验证环入口算法时构造一个“入口在链表头”的环和一个“入口在中段”的环环长一奇一偶把两种情况都测通了代码基本就稳了。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
