环形链表 II 这道题讲的是给定一个链表让你找出环的入口节点。如果不要求额外空间用哈希表一分钟就写完了一旦要求空间 O(1)就得掏出快慢指针这套经典解法。这篇文章会从题目拆解、Floyd 判圈算法的数学推导、三种语言实现细节、常见边界情况到扩展题型完整过一遍。不管是刚接触链表的新手还是准备面试想系统刷题的老手这一篇应该都能让你把这道题彻底吃透。1. 题目到底在问什么1.1 题干要点拆解原题的意思是给你一个链表的头节点 head链表中可能存在环。所谓环就是链表的某个节点的 next 指针指向了它前面已经出现过的节点导致遍历链表永远走不到尽头。题目要求你返回“环的入口节点”也就是这个环开始的那个节点。如果链表无环返回 null。这里最容易混淆的是不是让你判断“有没有环”而是让你找到“环的入口在哪里”。判断有没有环只需要检测快慢指针是否相遇那个题是第 141 题而第 142 题是在确认有环的基础上再多走一步精确定位环的起始点。换句话说141 题考的是“会相遇吗”142 题考的是“在哪里相遇”。光看题目表述很多人第一反应是我用哈希表记录每个经过的节点一旦遇到一个已经在哈希表里的节点它就是环的入口因为它是第一次重新回到的节点。这个思路完全正确也最容易理解。但题目通常有个更高的要求能否只使用 O(1) 的额外空间来解这个要求卡住了不少人也是这道题真正想考察的算法思维。1.2 和“判断是否有环”那题的区别第 141 题只要返回布尔值告诉你链表里有没有环。实现方案就是用快慢指针慢指针一次走一步快指针一次走两步如果链表有环快指针最终会“追上”慢指针如果无环快指针会先走到空节点。第 142 题在此基础上升级了。确认有环之后你还得返回环的起始节点。很多人以为“相遇的节点就是环的入口”这是最大的误区。快慢指针第一次相遇的节点只是环里的某个随机位置并不一定是环的入口。只有当链表头到环入口的距离恰好等于环长度一半的倍数时相遇点才会恰好在入口这是特例不是通法。所以 142 题的关键是在快慢指针相遇之后再推导出一个恒等式用一次“让慢指针从 head 重新出发快指针从相遇点继续前进”的过程最终找到入口。这一步是纯数学推导理解了它整道题就不再是背代码而是能现场推导出来的真本事。1.3 输入输出边界这类题在在线评测平台上链表结构已经定好的通常是struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };需要注意几个边界输入head 为 null也就是空链表直接返回 null。head.next 为 null也就是只有一个节点它不可能形成环返回 null。整个链表只有一个节点且自环即 head.next head那么环入口就是 head 自己。链表可能很长入口可能在很靠前的位置也可能就是第一个节点。这些边界看起来简单但代码里如果少写一个空指针判断运行时就直接崩。后面章节我会专门列出来。2. 解题前先想清楚的两条路2.1 用哈希表记录 visited最简单最稳定先讲最直接的方法。用一个哈希集合保存已经访问过的节点然后从 head 开始遍历。每走到一个节点先检查这个节点是否已经存在集合里如果存在说明这是一个“回头路”这个节点就是环的入口如果不存在就把它加入集合继续走。def detectCycle(head): seen set() cur head while cur: if cur in seen: return cur seen.add(cur) cur cur.next return None这个方案的时间复杂度是 O(n)空间复杂度也是 O(n)。当 n 很大时额外内存占用会比较明显。而且哈希表的开销也不小尤其是链表节点多、node 对象又大的时候set 里的内存增长很快。但哈希表解法有一个不容忽视的优点它不依赖任何数学推导逻辑极其直观。面试中如果考官允许用额外空间或者你一时想不起来快慢指针的推导先答出哈希表解法再逐步优化反而显得思路清晰。我见过不少候选人一上来就写快慢指针但代码写错了反而不如先给 O(n) 空间解法再分析如何优化成 O(1)。2.2 用快慢指针找入口常数空间的经典做法快慢指针的思路分两个阶段。第一阶段是判环slow 从 head 出发每次走一步fast 也从 head 出发每次走两步。如果链表有环那么 fast 必然比 slow 多走一些路程最终会在环内某一点追上 slow这就是第一次相遇。如果无环fast 会先遇到 null直接结束。第二阶段是找入口在第一次相遇的点让一个指针从 head 重新出发每次都走一步另一个指针继续从相遇点出发也每次走一步。两者再次相遇的位置就是环的入口。第二阶段为什么能保证相遇在入口这是 Floyd 判圈算法也叫托ortoise and hare 算法的核心后面的数学推导部分会详细展开。但先记住结论相遇点“绕回入口的距离”等于链表头到入口的距离。相当于两个等速指针一个从起点走一个从相遇点走最终会在入口碰头。这个算法的总时间仍然是 O(n)空间 O(1)。因为两个指针最多走常数圈不会重复遍历太多遍。2.3 为什么不是“第一次相遇的节点就是环节点”我见过很多人第一次学到这里会很困惑。明明快慢指针都相遇了为什么不直接返回这个节点举一个具体例子你就明白了。假设链表头到环入口距离是 7环长度是 4。slow 走一步fast 走两步。当 slow 走到入口时它走了 7 步fast 走了 14 步也就是绕完 7/4 1 圈多 2 步其实这里 fast 已经入环走了 7 步换算成环内位置是距入口 3。继续走下去slow 入环fast 继续追最终相遇点在环内某个位置。如果环长度不是 7 的因子之类的话相遇点基本不会是入口。所以“第一次相遇点”只是一次追及过程的自然结果跟入口位置没有直接关系。要想得到入口必须再做一次数学推导。这也是这道题区分“会背模板”和“真正理解算法”的地方。3. Floyd 判圈算法的数学内幕3.1 两阶段的本质判环与找入口Floyd 判圈算法对环的检测思路本质上和“两人绕操场跑步速度快的人追上了速度慢的人”是一回事。没有环的链表就是一条直线跑道速度快的先跑到终点有环的链表就是环形跑道速度快的总会在某一圈套圈追上速度慢的人。而找入口这个阶段利用了“长度相等”的性质。把链表头到入口的距离记为 a入口到第一次相遇点的距离记为 b第一次相遇点继续走回入口的距离记为 c环长度就是 b c。利用 fast 走过的距离是 slow 的两倍可以推出 a 与 c 的关系进而设计出从 head 和相遇点同时走一步的解法。这部分公式很多人见过但未必能完全理解每个符号的意义。下一节我会把每一步拆开用文字替代冗长公式来推一遍。3.2 相遇位置推导a、b、c 的含义先定义三个关键变量假设链表有环a从链表头到环入口的节点数也可以理解成直线段长度。b从环入口出发沿着 next 方向走到第一次相遇点所经过的节点数。c从第一次相遇点继续沿着 next 方向走回到环入口所经过的节点数。那么整个环的长度 L b c。现在开始让 slow 和 fast 从 head 同时出发。slow 速度为 1fast 速度为 2。当两者第一次相遇时假设 slow 一共走了 s 步fast 走了 2s 步。slow 走到相遇点的路程是 a b因为 slow 从链表头出发走过直线段 a进入环后再走 b 就到达相遇点。fast 走到相遇点的路程是 a b kL其中 k 是 fast 在环内多绕的完整圈数它可能在追上 slow 之前绕了好几圈这是个未知的正整数至少为 1。因为 fast 的路程是 slow 的两倍所以有2 * (a b) a b kL化简得a b kL也就是 a b 恰好等于环长度的整数倍。移项后得到a kL - b而 kL - b 又可以写成 (k-1)L (L - b)因为 L b c所以 L - b c因此a (k-1)L c这个式子说明从链表头走到环入口的距离 a等于“从相遇点继续往前走 c 步回到入口然后再绕 (k-1) 圈”的距离。进一步简化就是从相遇点走 c 步回到环入口和从链表头走 a 步到环入口两条路走完最终都到同一个点。3.3 关键恒等式从相遇点走到入口 从头走到入口上面的恒等式 a (k-1)L c 是整套解法的发动机。你可以想象有两个人站在两个地方一个人站在链表头另一个人站在第一次相遇点。两个人以完全相同的速度往前走每次都走一步。链表头的那个人要走 a 步才能到环入口而相遇点的那个人要走 c 步就能到环入口。如果 a 恰好等于 c那没问题但一般情况下 a 不等于 c。不过定理说的是相遇点的人如果走 a 步会走到哪里相遇点走 c 步到达入口再走 (k-1)L 步也就是绕回去又回到入口所以从相遇点走 a 步也正好到达环入口。这就意味着只要让两个指针以同样的速度向前走一个从链表头出发一个从相遇点出发他们必然会在环入口相遇。这就是第二阶段算法的依据slow 重新指向 headfast 保持在相遇点两者每次走一步直到 slow fast这个节点就是环的入口。这个推导最妙的地方在于我们根本不需要知道 k 是多少也不需要知道 a、b、c 的具体数值只需要知道相等的结论就能写代码。这也是算法笔记里常说的“数学一塌糊涂但代码两行”的原因推导复杂实现极其简练。3.4 快指针为什么走两步不走三步一个自然的问题是为什么 fast 每次走两步而不是三步、四步走三步不也能追到 slow 吗答案是走三步在“判环”阶段确实也能追上也一定能追上但在环很小的情况下快指针可能连续跨过慢指针所在的节点导致“没有检测到相遇”吗这里需要认真理一下因为这里有个经典误会。在链表节点构成的离散世界里fast 如果一次走 3 步它会从某个节点直接跳到下三个节点。而 slow 只走了 1 步。如果下一时刻 fast 的落点正好等于 slow 的落点那能相遇但如果 fast 从 slow 头上“跳过去”了两者是不是就错过了实际上在环内fast 相对 slow 的速度是 2 步/时间单位如果 fast 走 3slow 走 1相对速度是 2相对速度为 2 意味着 fast 每单位时间靠近 slow 两步。由于环长有限最终注定会落到同一点。即使 fast 曾经从 slow 头上跳过去因为相对速度恒定为 2它会在后续追上。所以走 3 步理论上也能实现判环。但为什么标准解法都用两步关键是后续找入口的推导。如果 fast 走 3 步第一次相遇时fast 走过的距离是 slow 的 3 倍推导出的公式就不再是 a (k-1)L c 这么简洁而是会多出一个和步长相关的余数条件。不同的步长会得到不同的“相遇点重新出发”策略推导起来复杂而且容易出错。走 2 步就是最经典、推导最简洁、实现也最安全的选择。另外从实际效率来说fast 走 2 步已经能保证在慢指针走完一个环的长度前追上效率已经很高继续加步长没有收益。4. 三种语言的实现与细节4.1 Python 实现写起来最舒服class ListNode: def __init__(self, x): self.val x self.next None def detectCycle(head): if not head or not head.next: return None slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: start head while start is not slow: start start.next slow slow.next return start return NonePython 版本注意三件事。第一判断初始空链表时用 not head 或 not head.next不要用 head None 这种写法虽然也能运行但不够 Pythonic。第二判断两个节点是否相同用 is 而不是 。链表节点对象是引用类型is 比较的是内存地址这和我们找“同一个节点”的目标完全一致而 在大多数自定义实现下会走对象默认比较也可能比较值容易出岔子。第三while 条件 fast and fast.next如果没有 fast.next 的检查在链表长度为偶数、无环的情况下fast.next 会变成 None下一轮 fast.next.next 就会抛异常。4.2 Java 实现空指针是最大的敌人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) { ListNode start head; while (start ! slow) { start start.next; slow slow.next; } return start; } } return null; } }Java 版本最容易翻车的点就是 fast.next.next。while 循环的终止条件已经写了 fast ! null fast.next ! null这意味着在循环体里访问 fast.next.next 是安全的。因为 fast.next 不为空fast.next.next 有可能是 null但访问是允许的只是下一轮循环会因 fast null 或 fast.next null 退出不会出问题。另一个很多初学者犯的错误是在结束判环循环后没有写 return null。Java 编译会直接报错缺少返回值。因为编译器能看出来 while 有可能一次都不执行或者正常退出所以必须在方法末尾补上 return null。4.3 C 实现指针操作的快感class Solution { public: ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return nullptr; } ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode *start head; while (start ! slow) { start start-next; slow slow-next; } return start; } } return nullptr; } };C 版本和 Java 版本几乎是同构的但有一个很小的区别有人喜欢把 head nullptr 和 head-next nullptr 合并成 if (!head || !head-next)。这个写法能用但可读性一般尤其对刚转 C 的人建议写成显式 nullptr 比较。另外在 C 里节点对象是手动 new 出来的算法本身不负责 delete所以无需考虑内存释放问题只需要保证遍历时不访问空指针。4.4 容易被忽略的空指针与边界刚才三个版本里头部的边界检查都是同一个套路head 为空或者 head.next 为空直接返回 null。为什么 head.next 为空也要直接返回因为只有一个节点的链表不可能有环除非自环但自环时 head.next head这在 head.next 不为空的前提下是成立的所以需要区分。实际上head.next null 说明只有一个节点无环head.next head 说明自环这属于 head.next 不为 null 的情况会进入主循环并由后续逻辑处理。还有一个容易被忽略的边界链表无环时主循环正常退出返回 null。有些初学者会在循环外面随手写 return head这显然是错的。我在实际刷题时有一个小习惯写完代码后先手动模拟空链表、单节点无环、单节点自环、双节点无环、双节点自环、长链表有环入口在第一个节点等几个极端样例。这几个样例跑通了基本就不会有低级错误。5. 现场实战几个典型样例走一遍5.1 样例1有环入口在中间假设链表是这样的3 - 2 - 0 - -4 ^ | |_________|也就是 -4 的 next 指向 2环入口是节点 2。链表头到入口 a 1环由 2、0、-4 三个节点组成环长度 L 3。慢指针和快指针都从 3 出发。slow 走一步到 2fast 走两步到 0。slow 到 0fast 到 -4。slow 到 -4fast 走两步先到 2再到 0。此时 slow 在 -4fast 在 0还没相遇。slow 到 2fast 到 -4相遇点在 -4。此时执行第二阶段start 从 head 出发slow 继续从相遇点 -4 出发两个都每次走一步。start 下一步到 2slow 下一步到 2相遇返回 2。正好是环入口。如果还有疑虑可以继续推start 从 head 到 entry 走了 a1 步slow 从相遇点走 c 步c 是相遇点到入口这里 c -4 - 2正好是 1 步所以同时到达。这个例子的 a 和 c 恰好相等可能不太有说服力。换个数据。5.2 样例2整个链表就是环另一种情况链表头就是环入口。比如1 - 2 - 3 - 1a 0环长度 L 3。slow 和 fast 从 1 出发。slow 到 2fast 到 3。slow 到 3fast 到 2。slow 到 1fast 到 1第一次相遇在 1。第二阶段start 从 head也就是 1出发slow 从相遇点也是 1出发两者一上来就相等直接返回 1。环入口就是 head 本身符合预期。如果整个链表首尾相接第二阶段的 while 循环一次都不用执行函数直接返回 head。这种边界情况恰恰是很多代码容易写错的地方因为有人会把 start 初始化为 head.next或者误以为必须进入循环才能找到入口。5.3 样例3自环自环是最好玩的边界只有一个节点并且这个节点的 next 指向自己。head.next head所以环入口就是 head。进入主循环slow 和 fast 都从 head 出发。slow slow.next 得到 headfast fast.next.next 也得到 head第一次相遇就是 head。第二阶段 start headslow head直接相遇返回 head。整个过程没有一步多余。如果前面头部检查写成了 if (head null || head.next null) return null自环反而没被拦住因为 head.next 是 head不是 null。很好这个检查逻辑是安全的。6. 常见问题与踩坑记录6.1 为什么 fast 初始指向 head 而不是 head.next网上很多版本的代码会把 fast 初始化为 head.nextslow 初始化为 head这样做的原因是让循环一开始就不同步方便在 while 里判断。这种写法也能通过题目但第二阶段找入口时相遇点的含义会有细微变化推导起来不如统一初始化为 head 来得干净。统一把 slow 和 fast 都初始化为 head代码更对称语义也更清晰。在进入循环前需要确保 head 不为空且 head.next 不为空否则 fast.next.next 会出问题。统一从 head 出发还有一个好处如果链表无环slow 和 fast 的移动逻辑对称不容易把自己绕晕。我的建议是始终用同一套初始状态省得在不同写法之间来回切换。6.2 死循环与超时有些人在判环阶段没有写 while 条件的空指针检查或者把循环条件写错导致链表无环时 fast 走到 null 还继续访问 fast.next直接抛异常。更隐蔽的问题是如果 fast 的移动步长随意设置比如一次走 3 步在环很长时确实也能相遇但环长和步长之间的数学关系不清晰可能让循环次数增加甚至在某些极端构造下变得极慢。标准解法不会死循环因为只要存在环快慢指针必然相遇不存在环循环会自然退出。但如果你改了步长或者初始位置就需要重新推导。我记得有一次为了测试用了 fast 走一步、slow 走一步的等速指针结果在有环的链表里两个指针永远不相遇死循环最后超时。那次经历让我彻底明白等速指针只会保持相对静止判不了环。6.3 返回值到底返回哪个节点第二阶段里有两个指针一个是 start 从 head 出发另一个是 slow 从相遇点出发。当它们相等时返回哪一个都可以因为此时它们指向同一个节点。但要注意第二阶段里 slow 不能改名为 faster 或者其他容易混淆的名字否则代码读起来很别扭。还有有人会把 start 写成 third或者 fast2然后想着“fast2 是从 fast 那边来的应该和 slow 保持一致”。只要逻辑清楚名字随意。我见过一份代码里第二阶段用的是另一个指针 qq 从相遇点出发p 从 head 出发最后返回 p。这样也正确只是可读性差一些。关键是理解第二阶段的两个指针速度都是 1起点分别是 head 和第一次相遇点。6.4 快指针步长选 2 的替代方案如果非要用快指针步长 3判环阶段一样可行。你还得额外考虑如果环长和步长之间满足某种关系第一次相遇点对应的 c 值和 a 值的关系会变化第二阶段就不能再用“两指针各走一步”的简单办法可能需要走更多步才能找到入口。这会让代码复杂度上升而且面试时推导这个公式的时间成本太高。所以我的结论是标准方案就是最快、最稳、最好理解的方案。步骤变来变去反而容易出错。做题不是为了炫技而是为了在最短时间内给出正确且能解释清楚的方案。7. 从这一题延伸出去7.1 环的长度怎么求既然已经能定位环的入口求环的长度就很简单了。找到环入口之后在入口处停一个指针然后每次走一步并计数直到重新回到环入口计数结果就是环的长度。这个操作的时间复杂度是 O(L)其中 L 是环的节点数。还有另一个方法在第一次相遇点处继续走每走一步计数再次回到相遇点时计数结果也是环长。因为第一次相遇点本来就在环内所以从这个点出发绕一圈必然回到自身。这个方法和从入口计数本质一样但代码里可以省一次第二阶段调用直接得到结果。如果你想在原来代码的基础上改我建议用第二种改动最小。def cycle_length(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: cur slow length 1 cur cur.next while cur is not slow: length 1 cur cur.next return length return 07.2 寻找重复数的隐藏解法有一个经典题目给你一个长度为 n1 的数组里面的数字都在 1 到 n 范围内假设只有一个重复的数字让你找出来。要求不能修改数组也只能用常数空间。正常思路是二分或者位运算但更巧妙的是把它转化成链表问题把数组下标看成节点下标 i 对应的值 nums[i] 看成 next 指针。因为存在重复值必然有两个下标指向同一个值而这个值就是环入口。利用这道题学到的快慢指针找入口方法可以直接求出重复数。我第一次看到这个转化时确实拍案叫绝因为链表的快慢指针算法居然能跑到数组里。这其实说明了快慢指针找环的本质不是链表特有的算法而是“函数迭代轨迹”上的判圈算法。只要你能把数据组织成 f(x) 的迭代形式就可以用。7.3 链表交点问题与环的联系另一个常见题型是求两个链表的交点。常规做法是用两个指针分别遍历两个链表如果相交就返回交点。这个题目还有一个思路是把其中一个链表的尾部接到另一个链表的头部构造出一个环然后用环形链表的入口算法来找交点。虽然实际写代码时直接用双指针更简单但从原理上看环形链表的思路能加深对问题的理解。用这种方法思考你会发现fast 和 slow 在环里相遇的过程和两个链表指针交错的过程有相似之处。本质上都是“走不同的路最终殊途同归”。7.4 关于空间复杂度优化的心得这道题最核心的收获不是背下来一个算法而是理解“空间换时间”和“时间换空间”的权衡。哈希表解法空间复杂度 O(n)但代码直观几乎不用解释快慢指针解法空间复杂度 O(1)但需要数学推导。很多人在面试时会不自觉偏向哈希表因为安全、不容易出错。但如果题目明确要求空间 O(1)就必须掌握快慢指针。我的建议是两种解法都要练会并且能在一分钟内从哈希表解法切换到快慢指针解法。因为面试官很喜欢先让你用哈希表做然后问“能不能不用额外空间”。如果你能当场推演 Floyd 算法而不是磕磕绊绊背代码印象分会高出不少。8. 这段推导值得反复咀嚼这道题看起来只有短短几行代码背后却藏了一整套数学推导。我最早学的时候也是先背了代码后来某一次在纸上画链表演示时才真正理解 a (k-1)L c 的意思。从那以后哪怕几个月不写这段代码我也能在几分钟内重新推回来。这比记忆代码要可靠得多。如果让我给一个学习路径的建议那就是先画图。拿纸笔随便画一个有环链表标出 a、b、c然后手动模拟 slow 和 fast 的移动过程。多模拟几轮之后你会发现“快指针多走的路程 慢指针路程的两倍”这句话是整道题的钥匙。等这个式子刻在脑子里第二阶段的两个指针为什么要从不同起点出发就再也不会忘记了。最后再分享一个实际排查中的小技巧写跑题主循环后先在脑子模拟一个无环链表的例子确保循环能退出再模拟一个有环链表确保第二阶段不会死循环。这两个都是极简单但极有效的自测方式。毕竟这种链表题debug 起来不像数组题那么直观日志都不容易打逻辑正确性只能在写代码时确保。