1. 这道题到底在考什么环形链表II的常见误区和真正的解题思路环形链表这组题在力扣里的地位不用我多说hot100的常客面试高频。第一题只是让你判断链表有没有环很多人在第二题就卡住了不仅要知道有没有环还要返回环的入口节点。所以《力扣hot100》里的这道142题表面看只是加了一个“返回入口”的需求实际上把整个问题的难度从“能不能想到快慢指针”提升到了“能不能把数学关系讲清楚”。我先说一个最常见的误区。很多人第一次做这道题时会想当然地认为快慢指针相遇的地方就是环的入口。理由是“快指针追上慢指针那追上的位置自然就是环开始的位置”。这个直觉听上去很合理但实际是错的。你可以自己构造一个简单的例子验证链表从头部到环入口走3步环本身走4步快慢指针第一次相遇的位置根本不在入口节点上。这就是为什么第一题会做第二题依然会懵——因为相遇点只是“环存在的证据”不是“入口的答案”。那正确的解题方向是什么其实就两条路一是用哈希表记录访问过的节点空间换时间二是用快慢指针加一步数学推导做到常数空间。前者写起来几乎没有思考成本后者才是这类题真正想考察的东西也是面试官最容易追问的部分。我的建议很直接哈希表法可以用来保底但快慢指针法必须弄懂因为它才是这道题的本质也是你从“会背题”变成“会讲题”的分水岭。这道题适合谁如果你是正在刷题的求职者或者想系统整理链表题型的老手这篇文章里我会把推导过程完整写出来不跳跃不省步骤保证你能在纸上自己推一遍然后彻底记住。2. 快慢指针解法两行代码背后的完整推导2.1 为什么快指针每次走两步慢指针每次走一步快慢指针的核心思路是用两个不同速度的指针在链表上游走利用“速度差”制造相遇。如果链表里没有环快指针会先走到空节点问题直接判定结束如果有环快慢指针最终会进入同一个环里转圈因为快指针比慢指针每轮多走一步所以它迟早会追上慢指针。这里有个细节值得停下来想一想为什么是“每次多走一步”如果快指针每次走三步、慢指针每次走一步行不行从纯数学上说只要速度不同理论上都有可能相遇但工程上没人这么写。原因有二第一每次多走一步会让“追及”过程太复杂相遇位置取决于环长和速度差的整除关系甚至可能跳过去产生难以预测的行为第二链表节点的访问受空指针限制快指针一次跨太多写判空条件时非常容易漏掉“快指针可能一下子越过null”的情况。所以两格一步、一格一步是经过无数人验证的稳定选择面试里直接按这个来不会错。还有一个更基础的问题为什么两个指针要同时从head出发而不是一个先跑、一个再出发因为同时出发才方便用下面的数学关系推导入口位置。很多题解在这里喜欢直接抛结论但如果你不明白推导代码一旦变形就会不知所措。2.2 相遇之后为什么要“再来一次”入口位置的数学证明这是整道题的灵魂。先说结论快指针和慢指针第一次相遇后把一个指针放回head另一个留在相遇点然后两个指针都改成每次走一步继续往前走它们再次相遇的位置就是环的入口节点。这个结论听起来像魔法但推一遍就清楚了。我习惯把链表画成三段来理解变量也按主流题解的约定来命名a链表头节点到环入口节点的距离也就是不入环的“直段长度”b环入口节点到快慢指针第一次相遇节点的距离c相遇节点继续走到环入口节点的距离环的周长C b c。假设两个指针从head同时出发慢指针每次走1步快指针每次走2步。第一次相遇时慢指针一共走了a b快指针一共走了a b n*C其中n是快指针在环里比慢指针多绕的整圈数。因为快指针走过的路程是慢指针的2倍所以2 * (a b) a b n * C移项化简a b n * C也就是a n * C - b (n - 1) * C (C - b) (n - 1) * C c你注意最后一个等号C - b就是c也就是从相遇点继续走到入口的距离。所以这个式子翻译成大白话就是从head走a步到达入口等于从相遇点先走c步到达入口再在环里绕n-1圈后又回到入口。反正最后都会落在入口节点上。既然如此让一个指针从head开始走a步另一个指针从相遇点开始走a步二者必然在入口汇合。很多人在这里会卡住为什么要绕n-1圈也能成立因为环是闭合的绕完一整圈还会回到同一个节点所以“多绕几圈”在这个问题上完全不影响结果。这也解释了一个很有趣的现象即使n不管等于几这个规律都成立。你用最极端的n 1来想就是a c更直白。2.3 整个过程的伪代码与整体逻辑把上面的思想转成步骤其实就五句话初始化slow headfast head循环条件是fast ! null fast.next ! null每次让slow走一步、fast走两步如果循环退出说明链表无环返回null如果slow fast说明有环此时fast留在原地slow回到head两个指针都每次走一步再一次相遇的节点就是入口返回该节点。这个算法的空间复杂度是O(1)时间复杂度是O(n)因为快指针最多走完整条链表两次左右。实测里不管链表多长这个算法都能在线性时间里跑完不会因为环很大或链很长而退化。3. 边界条件和测试用例最容易写出Bug的地方3.1 空链表、单节点、完全无环的情况算法题最怕的不是没思路而是思路对了但边界条件没处理好。对于这道题最简单的边界就是空链表和单节点链表。空链表即head null直接返回null只有一个节点且head.next null也直接返回null。很多人在面试时容易一上来就写while (fast ! null fast.next ! null)这个条件本身就包含了空链表的情况因为fast是null时循环根本不会进入所以问题不大。真正容易翻车的是如果fast.next为null但你还要在循环里访问fast.next.next就会抛空指针。因此循环条件里必须同时满足fast ! null和fast.next ! null顺序也不要颠倒否则某个语言可能会报错。再看完全无环的链表比如一个正常的1 - 2 - 3 - 4 - null。快指针会先走到末尾循环退出函数返回null。这里没有歧义但实际写代码时最好在纸上把快指针的走向画一下确认它不会在倒数第二个节点那里出事。3.2 环在头部、环在中间、自环有环的情况里我个人认为最值得测试的是“环入口正好是head”的情况。比如链表1 - 2 - 3 - 2入口节点是2不是head但如果链表是1 - 1这种自环入口就是head本身。自环的情况非常容易验证数学推导a 0所以从head出发的指针一开始就在入口而相遇点绕回去的距离c也必然是0两者理所当然在入口相遇。环在中间的情况是最常见的也最能检验你对推导的理解。我自己刷题时习惯构造一个长度5的链表让环从第3个节点开始手动走一遍快慢指针确认相遇点不是入口然后再执行“第二次遍历”验证最后确实在第3个节点汇合。这个方法笨但非常有效建议你也试试。3.3 快慢指针循环条件的注意点说到循环条件还有一个隐藏的坑第一次寻找相遇点时不能用slow ! fast作为循环条件因为一开始slow和fast都等于head循环直接不进入结果就错了。正确做法是“判断是否到达链表末尾而不是判断是否相遇”等循环内部检测到slow fast时再break或者return。这一点看起来小儿科但我见过不少人在白板上写这道题时翻车原因就是没有把“初始状态相等”和“过程相遇”这两件事区分开。处理二次遍历时也要小心。一个指针回到head之后另一个指针留在相遇点这时两者距离可能非常远也可能就在同一个节点。无论哪种情况都直接进入while (slow ! fast)的循环让它们一步步走不要中途改变步长。记住从这一刻起两个指针的速度完全一致都是每次走一步否则整个推导就失效了。4. 完整实现代码Java、Python、C三份参考4.1 Java实现力扣上最常用的语言就是Java我直接给出一个适配力扣ListNode定义的版本public class Solution { public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { // 有环开始找入口 slow head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } } return null; } }这段代码的要点在于第一次循环里找到相遇点后直接把slow重置到head然后进入第二个循环。第二次循环不需要判空因为我们已经确定链表有环两个指针永远不可能走到null它们最终一定会在入口相遇。很多题解会在第二个循环里写fast ! null之类的条件其实是多余的反而干扰阅读。4.2 Python实现Python的写法会更简洁一些class Solution: def detectCycle(self, head: ListNode) - ListNode: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: slow head while slow is not fast: slow slow.next fast fast.next return slow return NonePython里判断两个节点是否相同记住要用is而不是。虽然ListNode默认没有重写__eq__时两者效果一样但用is在语义上更准确也避免某些语言里对象比较的歧义。4.3 C实现C版本和Java几乎一样只是指针访问方式稍有区别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) { slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } } return nullptr; } };4.4 代码细节说明如果你仔细对比三份代码就会发现核心逻辑完全一致区别只在语言本身的语法。这里我想额外说一个很多教程不会提的点这道题存在“一种看起来更省事但实际上有隐患”的写法就是先计算出环的长度再用长度去定位入口。具体来说你可以通过相遇点再走一圈算出环长C然后让一个指针先走C步另一个指针从head出发两者速度一致地走相遇点也是入口。这个写法同样正确但多了一次遍历而且代码逻辑比“一指针回head”版本复杂完全没有必要。面试时直接用“回head法”简洁且推导链最短。还有一个细节值得注意在Java和C版本里head.next null的判断其实可以省掉因为head不为空但head.next为空时fast.next为null循环条件中的fast ! null fast.next ! null自然不成立。不过我在力扣上实测过有些旧版本的判题环境可能会对某些写法更敏感所以保险起见开头加一个head.next null的判断没有坏处代码可读性也不会降低。5. 面试时怎么讲从代码到表达的思路梳理5.1 30秒讲清楚证明过程做题是一回事面试时讲清楚是另一回事。很多候选人代码写得很快但被问到“为什么第二次两个指针一定会在入口相遇”时就卡壳了。我建议你按以下顺序组织语言基本30秒内能讲完第一步定义清楚变量从head到环入口距离为a相遇点到入口距离为c环周长为C。第二步说明第一次相遇时快指针路程是慢指针的两倍列出等式2 * (a b) a b n*C。第三步化简得到a (n-1)*C c所以一个指针从head出发走a步和一个指针从相遇点出发走a步殊途同归都会到达入口节点。最后补充一句因为第二次两个指针速度相同所以它们会同时到达入口的位置。这套话术熟练以后面试官基本不会再追问这个问题。5.2 面试官追问的进阶问题这道题的追问方向通常就这么几个如果不允许用额外空间你怎么做答快慢指针法空间O(1)。如果允许用额外空间有没有更简单的写法答哈希表记录访问过的节点遇到第一个重复节点就是入口。环长怎么求答从相遇点出发再走一圈回到相遇点走过的步数就是环长。为什么快指针每次走两步而不是更多答两步保证一定能追上并且判空简单逻辑清晰。我见过最狠的追问是如果快指针每次走三步还能保证相遇吗这个问题其实是个坑。在有些环结构里快指针会反复跳过慢指针永远不相遇。所以不要主动说你试过走三步除非你能证明“每次多走一步”和“固定多走两步”在追及问题上的本质差别。面试时老老实实说“两步是经典且稳妥的选择工程上不需要冒进”就够了。5.3 快慢指针思路的举一反三快慢指针绝不只是为这一道题服务的。它最常见的三个变体是判断链表是否有环、寻找链表中间节点、寻找链表的倒数第k个节点。这几道题在力扣上都有对应的原题比如876题“链表的中间结点”、19题“删除链表的倒数第N个结点”。你会发现一旦掌握了“两个指针同向移动、速度不同或起点不同”的思想这些题基本属于同一类解题框架。我刷题时有个习惯每做完一道快慢指针题就把同类型的两三道拉出来一起对比总结它们的共性——一个是“倍速差制造相遇”一个是“先走k步制造位移差”。这种横向对比比单纯刷数量有效得多。6. 我的刷题心得这道题适合反复练习的三层价值6.1 第一层两个算法结论的记忆第一层是你至少要记住两个结论第一判断有没有环用快慢指针相遇即有环第二找入口把一个指针放回head另一个留在相遇点同速走再次相遇即为入口。这两个结论本身并不难背但只背结论不推导的话过两周大概率就会忘。我不止一次在评论区看人说“明明刷过142题面试时还是写不出来”原因就是背答案式刷题。结论可以记但推导过程也要能自己在纸上推出来否则面试官问一句“为什么”你的整个知识体系就崩塌了。6.2 第二层数学推导的内化第二层就是前面那套a (n-1)*C c的推导。你可能会觉得这不过是初中数学的移项有什么可内化的但实际很多人推得出来却不好意思在面试中讲因为不知道用什么语言组织。我的建议是先在纸上写三遍推导然后用口语复述一遍假装面前坐着一个人完整解释给他听。这听起来有点傻但效果很好。刷题本质上是“手到、眼到、口到”前面两个做到了最后那个往往被忽略而它恰恰是面试最需要的。6.3 第三层环形链表问题的思维模型第三层是建立“环形链表问题”的思维模型。环形链表相关的题不管怎么变核心就是几个要素是否成环、环的入口、环的长度。一旦你的脑子里有了“a、b、c、C”这四个变量的关系图几乎所有环形链表题都能在几分钟内套出解法。比如某道题让你判断两个链表是否相交本质上也可以转化为“把其中一个链表的首尾相连变成环再判断另一个链表是否有环”。这种思路迁移能力才是刷hot100真正的收获。所以我的个人建议是这道题不要只刷一遍。你可以在周末不查任何资料的情况下默写代码加默写推导直到一气呵成。写完之后再自己构造三五个链表用例画一遍确认每一步变量都对应上。这个过程总共花不了多少时间但对你的熟练度提升是立竿见影的。最后分享一个小技巧做这类题时我习惯把链表的结构画在草稿纸上而不是只在脑子里想象。尤其是快慢指针第一次相遇后整个人很容易绕晕但画出来之后“相遇点在环中的位置”和“入口在环中的位置”会一目了然。官方题解给的是标准思路画图才是自己的思考链路。希望这篇文章能帮你一次性把142题吃透后面遇到环形链表的变形题也能一眼看穿本质。