这道题我刷了三遍才彻底敢说“会了”不是因为它代码难写而是第一次过的人多半只是背下了答案没搞懂快慢指针相遇背后那层数学关系。每次面试前我周围总有同学临时抱佛脚翻这道环形链表2问“为什么相遇后从头再走一步就是入口”如果你也卡在这一步这篇题解记录就是给你写的。先说清楚这道题到底在解决什么给定一个链表如果链表中有环请返回环的入口节点如果无环返回null。注意这里的“2”指的是在判断“链表是否有环”的基础上进一步要求“找到入口那个节点”。相比环形链表1只需要返回布尔值环形链表2要把位置精确算出来。面试里这道题出现频率极高不只是因为它考链表操作更因为它能在一次提问里同时考察三件事指针操作基本功、数学推导能力、边界条件的考虑是否周全。很多人能写出哈希表解法但面试官紧接着问一句“空间复杂度O(1)怎么做”就卡住了。这篇记录我会从暴力解法开始再推导Floyd判圈算法的全过程最后用几个高频面试追问收尾。1. 题目到底在问什么——先读懂环形链表21.1 问题描述与输入输出分析题目描述其实很短给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。怎么判断有没有环题目给了一个定义如果链表中有某个节点可以通过连续跟踪next指针再次到达该节点则链表中存在环。这个定义看似绕其实就是在说链表里存在某个节点的next指向了它前面的某个节点形成一个圈。比如一条链表A-B-C-D-E其中E的next指向C那么从C开始C-D-E-C就永远走不完了。题目要求的“入口节点”就是这里的C。输入输出的形式在不同平台上略有差别有的直接返回节点对象有的要求返回一个索引。核心逻辑是一样的你只要把入口节点找到即可。如果链表中没有环返回null。举个很直接的例子3 - 2 - 0 - -4 ^ | |______________|节点-4的next指向节点2那么环的入口就是节点2。你从head出发走两步就到2而这个节点也是环的起点。1.2 这道题为什么值得反复刷坦白讲我第一次做这道题的时候觉得它“就是个数学题”跟链表操作关系不大。后来刷题刷多了才意识到这道题的价值恰恰在于它把链表遍历、指针移动、数学推导粘在了一起。面试官考这道题其实在观察两件事第一你知不知道用快慢指针判断环路第二你能不能推导出入口的位置而不是靠记忆硬背。我见过很多候选人能写出代码但被追问“为什么相遇后再走一段就能到入口”时支支吾吾说不清楚。这在面试中是致命的因为面试官真正想看的是思路不是默写代码。另外这道题的工程价值也很实在。在真实系统里链表结构的大量使用场景中检测环是常见需求——比如检测一个流程是否陷入死循环、判断一个状态是否会回到历史状态。理解Floyd判圈算法对你排查这类问题也有帮助。还有一点很现实这道题是面试高频题在算法题单里经常和环形链表1、相交链表、删除链表的倒数第N个节点放在同一个“链表指针操作”专题里。刷通这一题相当于把一类快慢指针题目的套路打通了。2. 朴素解法思路——哈希表方案2.1 哈希表方案的原理与分析在讲最优解法之前先聊最直观的方案。这个方案好理解也很容易写对从头开始遍历链表每经过一个节点就把它存进哈希表。如果遇到一个节点已经存在于哈希表中说明这个节点就是环的入口因为它被访问过两次。为什么这个方案能成立因为在一个没有环的链表里每个节点最多被访问一次遍历到最后必然遇到null。而一旦有环沿着next指针走总会走回某个已经走过的节点第一次“重复遇到”的那个节点恰好就是环的入口。时间复杂度方面这个方案是O(n)空间复杂度是O(n)。n是链表的节点数。这里的空间开销来自哈希表存储最坏情况下你要存储链表里的全部节点。用Python的set就可以轻松实现def detectCycle(head): visited set() cur head while cur: if cur in visited: return cur visited.add(cur) cur cur.next return None代码很短逻辑也很直接。但如果你去面试只给出这个解法大概率会收到一句追问能不能把空间复杂度降到O(1)2.2 哈希表方案的不足与优化方向哈希表方案的不足就一个字空间。当链表特别长或者说题目明确要求空间复杂度O(1)时这个方案就不满足要求了。面试中考查这道题通常期望的解法是空间复杂度O(1)的双指针方案。不过我也不建议直接跳过哈希表方案不谈。实际面试里先给出哈希表方案反而能展示你的思维层次先提出直观做法再优化到最优解比一步到位更能让面试官看到完整的思考过程。从哈希表方案联想到双指针方案关键点是我们需要一个“不依赖额外存储空间”的检测机制。而快慢指针就是这个机制的经典实现——慢指针每次走一步快指针每次走两步如果链表中存在环两个指针一定会在环内相遇。这里我插一句实在话如果你在面试时卡在双指针推导上可以先承认“我知道有更优的双指针解法但推导我可能需要整理一下”然后从哈希表方案开始讲再慢慢推导面试官通常不会直接否定这个思路反而会觉得你思路清晰不是背答案。3. Floyd判圈算法——双指针解法3.1 为什么快慢指针一定能相遇Floyd判圈算法的核心是定义两个指针slow每次移动一步fast每次移动两步。如果链表中没有环fast会先到达链表尾部null直接返回无环。如果链表中有环slow和fast最终一定会在环内相遇。这里有个很自然的疑问为什么一定会相遇直观理解是进入环之后fast每次比slow多走一步相当于fast在以一步的速度追赶slow环是有限的所以迟早会追上。严谨一点的推导是假设环的长度为L当两个指针都在环内时它们的相对速度是1步/次fast比slow多走一步。最坏情况下fast到slow的距离是L-1步那么最多经过L-1次移动两个指针就会重合。我第一次看到这个结论时还担心过“会不会快指针每次都正好跳过慢指针永远追不上”。实际上不会因为快指针的速度是慢指针的两倍每次都只多走一步在所有整数步数下它们的距离只会逐步缩小不会出现“跳过去”的情况。代码上判断循环终止有两种方式一种是判断fast和fast.next都不为null另一种是在循环里判断slow fast。要注意的是终止条件必须正确处理无环情况不能因为访问空指针而报错。3.2 相遇后再走一圈入口节点的数学推导这部分是整道题最核心的地方也是最多人似懂非懂的地方。设链表头部到环入口的距离为a环入口到slow和fast第一次相遇点的距离为b相遇点继续走到环入口的距离为c那么环长就是b c。当slow和fast相遇时slow走了a b步fast走了a b n(b c)步其中n是fast在环里多绕的圈数n 1。因为fast的速度是slow的两倍所以2(a b) a b n(b c)化简一下a b n(b c) a n(b c) - b a (n - 1)(b c) c这个式子的含义是从链表头部走到入口的距离a等于从相遇点继续走到入口的距离c再加上若干整圈。换句话说如果你现在让一个指针从head出发另一个指针从相遇点出发都保持每次走一步那么它们一定会在环入口处相遇。因为第一个指针走a步到达入口第二个指针走c步也到达入口而多走的那些整圈只是绕圈不改变到达的位置。这就是很多人背的结论“相遇后让一个指针从头节点重新出发另一个指针留在相遇点都以步长为1移动再次相遇的点就是入口”的由来。这个推导看着简单但自己讲一遍和看一遍感受完全不一样。我建议你合上书自己在纸上画一个链表示意图设几个具体数字比如a2b2c3推一遍。推完之后再去看代码会豁然开朗。3.3 完整代码实现Floyd判圈算法的代码不长但要写得干净、无空指针风险还是有几个细节要注意。我用Python写一版最直观的实现def detectCycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: # 相遇了说明有环开始找入口 ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptr return None这个版本的关键点有两个第一判断进环的循环条件是while fast and fast.next。首先要保证fast不是null才能访问fast.next其次要保证fast.next不是null才能访问fast.next.next。这个顺序不能反。fast每次走两步所以对于无环的奇数长度链表fast会恰好停在最后一个节点fast.next为null对于偶数长度链表fast会走到null。两种情况都会退出循环。第二找到相遇点之后ptr从head出发slow从相遇点出发。循环终止条件是ptr slow此时节点就是入口。注意此时不改变slow的移动速度还是每次一步。C版本也是面试高频需求我把核心部分也写出来class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode *ptr head; while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; } } return nullptr; } };顺手说一下有的同学会把慢指针在找入口阶段也重置为head然后两个指针从头一起走。这也是对的因为相遇后“slow从相遇点出发”和“从head出发”在数学上是等价的。但你如果不是很确定就按最稳定的方式写slow留在相遇点ptr从head出发。4. 边界条件与常见陷阱4.1 空链表、单节点与无环链表的处理边界条件是这道题的隐藏考点。很多时候算法思路对但边界忘处理一个用例就挂了。最常见的边界情况包括head为null直接返回null。上面的代码用while fast and fast.nexthead为null时循环不执行返回null天然正确。链表只有一个节点且无环head.next为nullfast.next为null循环条件不满足返回null。链表只有一个节点且self-loop即head.next指向自己slow和fast都会走回到head节点第一次循环就相遇然后ptr从head出发很快就找到入口就是head本身。普通无环长链表fast会先到null退出循环返回null。在处理这些边界时我习惯在写完代码后自己脑内跑一遍尤其是单节点自环的情况面试时这是很常见的“阴间用例”。还有一个容易搞错的地方如果链表无环fast指针会不会出现“跳过slow”的情况不会因为fast和slow的起点相同fast先进入链表深处如果走到尾部就出现null终止。只有在有环的情况下两者才会相遇。4.2 指针移动与死循环的隐患写双指针代码最怕的就是死循环。有几个细节需要特别注意第一循环条件里必须检查fast.next。一旦fast走到null或者fast.next是null说明链表没环直接退出。如果没有这一步在某个节点的next为null时访问fast.next.next会抛异常。第二找入口的第二段循环while ptr ! slow这段循环只在已经确定存在环的情况下执行所以理论上不会走到null。但如果你的代码在无环时也进入这段逻辑就会出问题。所以一定保证这段循环发生在slow fast判断之后。第三要注意“快指针每次走两步”的实现。有些同学写成fast fast.next.next但忘记在循环开头判断fast.next是否为null结果在链表只有两个节点时直接报错。我给的写法里while fast and fast.next已经保证了安全。还有一个值得注意的细节检测环入口时ptr和slow的步长都必须为1。如果你不小心让某个指针一次走了两步推导就不成立了。5. 从推导到面试表达——如何讲解解题思路5.1 面试官想听什么很多同学觉得面试遇到这题能写出最优解就稳了。其实不然。面试官会追问你的推导过程这是区分“会背题”和“真理解”的核心。我建议你在面试时按这个顺序讲第一步先说明为什么可以用快慢指针判断是否有环。强调快指针每次比慢指针多走一步进入环后一定会相遇。第二步画图推导入口公式。把链表拆成三段头到入口a、入口到相遇点b、相遇点到入口c。写出fast走的距离是slow的两倍这个等式化简出a c (n-1)(bc)。第三步解释代码实现。指出第一段循环找相遇点第二段循环找入口。说明ptr从head出发、slow从相遇点出发每次一步相遇处就是入口。这个顺序背后有一个逻辑先是直觉理解然后是数学证明最后落到代码。面试官听下来就会觉得你不是背的是有完整思路的。5.2 常见追问与回答我根据自己的面试经验整理了几个这题的高频追问供你参考追问一如果不需要返回入口只判断有没有环代码怎么简化答案是把第二段循环去掉只保留快慢指针判断是否相遇。时间O(n)空间O(1)。追问二慢指针进环时快指针已经在环里绕了至少一圈吗是的。因为快指针速度是慢指针两倍慢指针从head走到入口需要a步这段时间内快指针走了2a步。如果a很大快指针可能已经绕了多圈但无论绕几圈最终都会在入口之后的某个位置相遇。追问三快慢指针相遇时慢指针在环里走了多少步慢指针从入环到第一次相遇最多走不到一整圈。因为快指针追赶慢指针的相对速度是1步/次环长如果为L慢指针最多走L-1步就会被追上。这个结论有时候会作为提示给到候选人。追问四如果链表很长且环很小相遇点距离入口可能很远吗可能很远。a和c的关系取决于具体链表。虽然a c n*L但a本身可以很大相遇点也可以离入口很远。这也说明了为什么不能在相遇点直接返回。这些追问看似零散实际都在考察你对距离关系的理解。平时刷题时多想想这些问题面试时就会自然很多。6. 扩展思考与刷题建议6.1 题目的变体与延伸环形链表这道题还有几个常见变体我分享一下我的刷题经验变体一求环的长度。找到相遇点后保持slow不动让fast每次走一步绕一圈回到slow的位置计数就是环长。这个变体考察的还是对环结构的理解。变体二如果题目要求返回入口的索引即节点在链表中的位置你需要在返回节点对象的同时记录一个全局计数器或者在节点类里加一个位置字段。这类问题在个别平台出现过思路本身不难但要注意实现方式。变体三判断两条链表是否相交。这题和环形链表2看着无关但用的思想一脉相承——把其中一条链表的尾部接到另一条链表的头部如果有交点构造出的链表就会成环。很多题解讲相交链表时都会拿环形链表来做类比。变体四快慢指针不局限于链表也可以用在数组里。比如检测一个数组是否满足某个循环替换关系思路是相通的。理解了Floyd判圈再看这类题会轻松很多。6.2 刷题时不要只看题解最后聊点刷题方法上的心得。我第一次做这题的时候看完题解觉得“懂了”关上书自己写写出来的代码没错但如果你问我为什么ptr从head出发能找到入口我答不上来只能复述“因为推导就是这样”。这种状态其实就是不会。我的建议是每道算法题看完题解后至少做三件事第一不看答案自己写一遍代码第二合上代码在纸上画图手动跑一个具体例子第三给自己讲一遍思路看看能不能讲顺。这题需要手动跑的具体例子我推荐构造一个长度大于1的环比如总节点数6个入口在第二个节点。这样a1环长4推导和代码都能验证。刷题这事尤其是面试高频题不在于刷多少遍而在于每一遍是否真的把原理搞透了。环形链表2这道题如果你能不看题解独立推导出a c (n-1)(bc)并且用O(1)空间把代码写对那这一类的双指针题你基本就过关了。以后遇到“判断链表是否有环”“找环入口”“找链表交点”“找链表倒数第k个节点”这一系列问题快慢指针这个工具你会用得非常顺手。至少对我来说这题彻底想明白之后再刷相交链表和删除倒数第N个节点都顺畅了很多。 
长河君 · 2026/10/21 15:16:25 · 阅读 1.2k 环形链表 II 详解：快慢指针与Floyd判圈算法的数学推导
这道题我刷了三遍才彻底敢说“会了”不是因为它代码难写而是第一次过的人多半只是背下了答案没搞懂快慢指针相遇背后那层数学关系。每次面试前我周围总有同学临时抱佛脚翻这道环形链表2问“为什么相遇后从头再走一步就是入口”如果你也卡在这一步这篇题解记录就是给你写的。先说清楚这道题到底在解决什么给定一个链表如果链表中有环请返回环的入口节点如果无环返回null。注意这里的“2”指的是在判断“链表是否有环”的基础上进一步要求“找到入口那个节点”。相比环形链表1只需要返回布尔值环形链表2要把位置精确算出来。面试里这道题出现频率极高不只是因为它考链表操作更因为它能在一次提问里同时考察三件事指针操作基本功、数学推导能力、边界条件的考虑是否周全。很多人能写出哈希表解法但面试官紧接着问一句“空间复杂度O(1)怎么做”就卡住了。这篇记录我会从暴力解法开始再推导Floyd判圈算法的全过程最后用几个高频面试追问收尾。1. 题目到底在问什么——先读懂环形链表21.1 问题描述与输入输出分析题目描述其实很短给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。怎么判断有没有环题目给了一个定义如果链表中有某个节点可以通过连续跟踪next指针再次到达该节点则链表中存在环。这个定义看似绕其实就是在说链表里存在某个节点的next指向了它前面的某个节点形成一个圈。比如一条链表A-B-C-D-E其中E的next指向C那么从C开始C-D-E-C就永远走不完了。题目要求的“入口节点”就是这里的C。输入输出的形式在不同平台上略有差别有的直接返回节点对象有的要求返回一个索引。核心逻辑是一样的你只要把入口节点找到即可。如果链表中没有环返回null。举个很直接的例子3 - 2 - 0 - -4 ^ | |______________|节点-4的next指向节点2那么环的入口就是节点2。你从head出发走两步就到2而这个节点也是环的起点。1.2 这道题为什么值得反复刷坦白讲我第一次做这道题的时候觉得它“就是个数学题”跟链表操作关系不大。后来刷题刷多了才意识到这道题的价值恰恰在于它把链表遍历、指针移动、数学推导粘在了一起。面试官考这道题其实在观察两件事第一你知不知道用快慢指针判断环路第二你能不能推导出入口的位置而不是靠记忆硬背。我见过很多候选人能写出代码但被追问“为什么相遇后再走一段就能到入口”时支支吾吾说不清楚。这在面试中是致命的因为面试官真正想看的是思路不是默写代码。另外这道题的工程价值也很实在。在真实系统里链表结构的大量使用场景中检测环是常见需求——比如检测一个流程是否陷入死循环、判断一个状态是否会回到历史状态。理解Floyd判圈算法对你排查这类问题也有帮助。还有一点很现实这道题是面试高频题在算法题单里经常和环形链表1、相交链表、删除链表的倒数第N个节点放在同一个“链表指针操作”专题里。刷通这一题相当于把一类快慢指针题目的套路打通了。2. 朴素解法思路——哈希表方案2.1 哈希表方案的原理与分析在讲最优解法之前先聊最直观的方案。这个方案好理解也很容易写对从头开始遍历链表每经过一个节点就把它存进哈希表。如果遇到一个节点已经存在于哈希表中说明这个节点就是环的入口因为它被访问过两次。为什么这个方案能成立因为在一个没有环的链表里每个节点最多被访问一次遍历到最后必然遇到null。而一旦有环沿着next指针走总会走回某个已经走过的节点第一次“重复遇到”的那个节点恰好就是环的入口。时间复杂度方面这个方案是O(n)空间复杂度是O(n)。n是链表的节点数。这里的空间开销来自哈希表存储最坏情况下你要存储链表里的全部节点。用Python的set就可以轻松实现def detectCycle(head): visited set() cur head while cur: if cur in visited: return cur visited.add(cur) cur cur.next return None代码很短逻辑也很直接。但如果你去面试只给出这个解法大概率会收到一句追问能不能把空间复杂度降到O(1)2.2 哈希表方案的不足与优化方向哈希表方案的不足就一个字空间。当链表特别长或者说题目明确要求空间复杂度O(1)时这个方案就不满足要求了。面试中考查这道题通常期望的解法是空间复杂度O(1)的双指针方案。不过我也不建议直接跳过哈希表方案不谈。实际面试里先给出哈希表方案反而能展示你的思维层次先提出直观做法再优化到最优解比一步到位更能让面试官看到完整的思考过程。从哈希表方案联想到双指针方案关键点是我们需要一个“不依赖额外存储空间”的检测机制。而快慢指针就是这个机制的经典实现——慢指针每次走一步快指针每次走两步如果链表中存在环两个指针一定会在环内相遇。这里我插一句实在话如果你在面试时卡在双指针推导上可以先承认“我知道有更优的双指针解法但推导我可能需要整理一下”然后从哈希表方案开始讲再慢慢推导面试官通常不会直接否定这个思路反而会觉得你思路清晰不是背答案。3. Floyd判圈算法——双指针解法3.1 为什么快慢指针一定能相遇Floyd判圈算法的核心是定义两个指针slow每次移动一步fast每次移动两步。如果链表中没有环fast会先到达链表尾部null直接返回无环。如果链表中有环slow和fast最终一定会在环内相遇。这里有个很自然的疑问为什么一定会相遇直观理解是进入环之后fast每次比slow多走一步相当于fast在以一步的速度追赶slow环是有限的所以迟早会追上。严谨一点的推导是假设环的长度为L当两个指针都在环内时它们的相对速度是1步/次fast比slow多走一步。最坏情况下fast到slow的距离是L-1步那么最多经过L-1次移动两个指针就会重合。我第一次看到这个结论时还担心过“会不会快指针每次都正好跳过慢指针永远追不上”。实际上不会因为快指针的速度是慢指针的两倍每次都只多走一步在所有整数步数下它们的距离只会逐步缩小不会出现“跳过去”的情况。代码上判断循环终止有两种方式一种是判断fast和fast.next都不为null另一种是在循环里判断slow fast。要注意的是终止条件必须正确处理无环情况不能因为访问空指针而报错。3.2 相遇后再走一圈入口节点的数学推导这部分是整道题最核心的地方也是最多人似懂非懂的地方。设链表头部到环入口的距离为a环入口到slow和fast第一次相遇点的距离为b相遇点继续走到环入口的距离为c那么环长就是b c。当slow和fast相遇时slow走了a b步fast走了a b n(b c)步其中n是fast在环里多绕的圈数n 1。因为fast的速度是slow的两倍所以2(a b) a b n(b c)化简一下a b n(b c) a n(b c) - b a (n - 1)(b c) c这个式子的含义是从链表头部走到入口的距离a等于从相遇点继续走到入口的距离c再加上若干整圈。换句话说如果你现在让一个指针从head出发另一个指针从相遇点出发都保持每次走一步那么它们一定会在环入口处相遇。因为第一个指针走a步到达入口第二个指针走c步也到达入口而多走的那些整圈只是绕圈不改变到达的位置。这就是很多人背的结论“相遇后让一个指针从头节点重新出发另一个指针留在相遇点都以步长为1移动再次相遇的点就是入口”的由来。这个推导看着简单但自己讲一遍和看一遍感受完全不一样。我建议你合上书自己在纸上画一个链表示意图设几个具体数字比如a2b2c3推一遍。推完之后再去看代码会豁然开朗。3.3 完整代码实现Floyd判圈算法的代码不长但要写得干净、无空指针风险还是有几个细节要注意。我用Python写一版最直观的实现def detectCycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: # 相遇了说明有环开始找入口 ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptr return None这个版本的关键点有两个第一判断进环的循环条件是while fast and fast.next。首先要保证fast不是null才能访问fast.next其次要保证fast.next不是null才能访问fast.next.next。这个顺序不能反。fast每次走两步所以对于无环的奇数长度链表fast会恰好停在最后一个节点fast.next为null对于偶数长度链表fast会走到null。两种情况都会退出循环。第二找到相遇点之后ptr从head出发slow从相遇点出发。循环终止条件是ptr slow此时节点就是入口。注意此时不改变slow的移动速度还是每次一步。C版本也是面试高频需求我把核心部分也写出来class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode *ptr head; while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; } } return nullptr; } };顺手说一下有的同学会把慢指针在找入口阶段也重置为head然后两个指针从头一起走。这也是对的因为相遇后“slow从相遇点出发”和“从head出发”在数学上是等价的。但你如果不是很确定就按最稳定的方式写slow留在相遇点ptr从head出发。4. 边界条件与常见陷阱4.1 空链表、单节点与无环链表的处理边界条件是这道题的隐藏考点。很多时候算法思路对但边界忘处理一个用例就挂了。最常见的边界情况包括head为null直接返回null。上面的代码用while fast and fast.nexthead为null时循环不执行返回null天然正确。链表只有一个节点且无环head.next为nullfast.next为null循环条件不满足返回null。链表只有一个节点且self-loop即head.next指向自己slow和fast都会走回到head节点第一次循环就相遇然后ptr从head出发很快就找到入口就是head本身。普通无环长链表fast会先到null退出循环返回null。在处理这些边界时我习惯在写完代码后自己脑内跑一遍尤其是单节点自环的情况面试时这是很常见的“阴间用例”。还有一个容易搞错的地方如果链表无环fast指针会不会出现“跳过slow”的情况不会因为fast和slow的起点相同fast先进入链表深处如果走到尾部就出现null终止。只有在有环的情况下两者才会相遇。4.2 指针移动与死循环的隐患写双指针代码最怕的就是死循环。有几个细节需要特别注意第一循环条件里必须检查fast.next。一旦fast走到null或者fast.next是null说明链表没环直接退出。如果没有这一步在某个节点的next为null时访问fast.next.next会抛异常。第二找入口的第二段循环while ptr ! slow这段循环只在已经确定存在环的情况下执行所以理论上不会走到null。但如果你的代码在无环时也进入这段逻辑就会出问题。所以一定保证这段循环发生在slow fast判断之后。第三要注意“快指针每次走两步”的实现。有些同学写成fast fast.next.next但忘记在循环开头判断fast.next是否为null结果在链表只有两个节点时直接报错。我给的写法里while fast and fast.next已经保证了安全。还有一个值得注意的细节检测环入口时ptr和slow的步长都必须为1。如果你不小心让某个指针一次走了两步推导就不成立了。5. 从推导到面试表达——如何讲解解题思路5.1 面试官想听什么很多同学觉得面试遇到这题能写出最优解就稳了。其实不然。面试官会追问你的推导过程这是区分“会背题”和“真理解”的核心。我建议你在面试时按这个顺序讲第一步先说明为什么可以用快慢指针判断是否有环。强调快指针每次比慢指针多走一步进入环后一定会相遇。第二步画图推导入口公式。把链表拆成三段头到入口a、入口到相遇点b、相遇点到入口c。写出fast走的距离是slow的两倍这个等式化简出a c (n-1)(bc)。第三步解释代码实现。指出第一段循环找相遇点第二段循环找入口。说明ptr从head出发、slow从相遇点出发每次一步相遇处就是入口。这个顺序背后有一个逻辑先是直觉理解然后是数学证明最后落到代码。面试官听下来就会觉得你不是背的是有完整思路的。5.2 常见追问与回答我根据自己的面试经验整理了几个这题的高频追问供你参考追问一如果不需要返回入口只判断有没有环代码怎么简化答案是把第二段循环去掉只保留快慢指针判断是否相遇。时间O(n)空间O(1)。追问二慢指针进环时快指针已经在环里绕了至少一圈吗是的。因为快指针速度是慢指针两倍慢指针从head走到入口需要a步这段时间内快指针走了2a步。如果a很大快指针可能已经绕了多圈但无论绕几圈最终都会在入口之后的某个位置相遇。追问三快慢指针相遇时慢指针在环里走了多少步慢指针从入环到第一次相遇最多走不到一整圈。因为快指针追赶慢指针的相对速度是1步/次环长如果为L慢指针最多走L-1步就会被追上。这个结论有时候会作为提示给到候选人。追问四如果链表很长且环很小相遇点距离入口可能很远吗可能很远。a和c的关系取决于具体链表。虽然a c n*L但a本身可以很大相遇点也可以离入口很远。这也说明了为什么不能在相遇点直接返回。这些追问看似零散实际都在考察你对距离关系的理解。平时刷题时多想想这些问题面试时就会自然很多。6. 扩展思考与刷题建议6.1 题目的变体与延伸环形链表这道题还有几个常见变体我分享一下我的刷题经验变体一求环的长度。找到相遇点后保持slow不动让fast每次走一步绕一圈回到slow的位置计数就是环长。这个变体考察的还是对环结构的理解。变体二如果题目要求返回入口的索引即节点在链表中的位置你需要在返回节点对象的同时记录一个全局计数器或者在节点类里加一个位置字段。这类问题在个别平台出现过思路本身不难但要注意实现方式。变体三判断两条链表是否相交。这题和环形链表2看着无关但用的思想一脉相承——把其中一条链表的尾部接到另一条链表的头部如果有交点构造出的链表就会成环。很多题解讲相交链表时都会拿环形链表来做类比。变体四快慢指针不局限于链表也可以用在数组里。比如检测一个数组是否满足某个循环替换关系思路是相通的。理解了Floyd判圈再看这类题会轻松很多。6.2 刷题时不要只看题解最后聊点刷题方法上的心得。我第一次做这题的时候看完题解觉得“懂了”关上书自己写写出来的代码没错但如果你问我为什么ptr从head出发能找到入口我答不上来只能复述“因为推导就是这样”。这种状态其实就是不会。我的建议是每道算法题看完题解后至少做三件事第一不看答案自己写一遍代码第二合上代码在纸上画图手动跑一个具体例子第三给自己讲一遍思路看看能不能讲顺。这题需要手动跑的具体例子我推荐构造一个长度大于1的环比如总节点数6个入口在第二个节点。这样a1环长4推导和代码都能验证。刷题这事尤其是面试高频题不在于刷多少遍而在于每一遍是否真的把原理搞透了。环形链表2这道题如果你能不看题解独立推导出a c (n-1)(bc)并且用O(1)空间把代码写对那这一类的双指针题你基本就过关了。以后遇到“判断链表是否有环”“找环入口”“找链表交点”“找链表倒数第k个节点”这一系列问题快慢指针这个工具你会用得非常顺手。至少对我来说这题彻底想明白之后再刷相交链表和删除倒数第N个节点都顺畅了很多。