很多同学在接触“快慢指针找环”这个经典问题时，都是靠背代码过关的。第一阶段：慢指针每次走一步，快指针每次走两步，如果两个指针相遇了，说明链表有环；第二阶段：把某个指针重置到链表头，再让两个指针一步一步走，第二次相遇的位置就是环入口。代码两三行就写完了，但真被问到“为什么要重置？重置后为什么一定会相遇到入口？”的时候，很多人就卡住了。我自己在面试别人时，这个问题问过很多次，能完整推导出来的人确实不多。这篇文章准备专门把“重置快/慢指针”这个动作讲透，同时把“找环”“找入口”“算环长”“找中间节点”“找倒数第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 都等于 head，fast.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。它的入口是节点3，L 等于2（从节点1走两步到节点3），环长 C 等于4（3 -> 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 重置到节点1，fast 留在节点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:1，fast先走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 都等于 head，fast.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。它的入口是节点3，L 等于2（从节点1走两步到节点3），环长 C 等于4（3 -> 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 重置到节点1，fast 留在节点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:1，fast先走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 标出来，自己算一次，比看十遍解析都管用。最后分享一个小技巧：验证环入口算法时，构造一个“入口在链表头”的环和一个“入口在中段”的环，环长一奇一偶，把两种情况都测通了，代码基本就稳了。