★ FEATURED ARTICLE 1. 先搞清楚LeetCode-142到底在问什么很多人把它当成141的加强版其实考点完全不同刷题刷到第135天大概率已经过了那种“今天看题解、明天忘干净”的阶段。LeetCode-142这道环形链表II之所以值得单独写一篇是因为它表面上是141的后续题但考察的东西已经完全变了。141只问你“链表有没有环”返回一个布尔值。你用快慢指针跑一趟两个指针相遇就返回true遇到null就返回false结束。但142要求你不仅判断“有没有环”还要求把“环的入口节点”找出来。很多人在这一步开始翻车——不是不会写代码而是写出来的代码能过OJ但根本讲不出为什么。面试官稍微追问一句“第二次相遇为什么一定在入口”场面就容易冷掉。这题的输入参数只有一个head链表节点定义是常见的单链表结构class ListNode: def __init__(self, x): self.val x self.next None输出要么是环入口节点要么是None。力扣编辑器里那行“pos”只是用来表示内部测试时环的入口位置并不是真正的入参别被它带偏。这道题真正麻烦的地方在于第一次用快慢指针找到相遇点后你距离正确答案还差一个关键的数学推理。很多解法文章喜欢直接甩结论——“把慢指针放回头部快指针留在相遇点两个都走一步再次相遇就是入口”。结论背下来很容易但如果你不知道这个结论是怎么来的面试时一旦被要求推导证明或者题目稍作变形就会暴露。所以我这篇文章的重点不是贴一段能AC的代码而是把“为什么”讲透。适合正在系统刷力扣的算法学习者也适合准备算法面试、希望能在白板上把这道题讲清楚的候选人。看完之后不仅能默写代码还能在面试官问起时顺手写一波推导这才是刷题的正确姿势。2. 快慢指针判环的运动学原理为什么速度差必须是1而不是其他数字先退一步说说快慢指针判环这件事本身。两个指针从head出发slow每次走1步fast每次走2步。如果链表没有环fast会先遇到null循环结束。如果链表有环fast进入环之后会在里面绕圈slow之后也进入环。因为fast比slow快所以本质上是一个环形跑道上的追及问题fast在后面追slow速度差是1跑道周长有限追赶一定会在某个时刻完成也就是两个指针相遇。这里有一个初学者经常忽略的关键点——fast比slow快多少直接决定了这个算法能不能成立。速度差必须正好是1也就是fast走2步、slow走1步是最经典的配置但不是随便选的。如果fast一次走3步速度差变成2那么在追上slow之前fast可能直接从slow所在的位置“跨”过去导致两个指针永远没有“slow fast”的时刻。举个极端例子环长是2fast和slow同向跑速度差是2那么fast每步都跳到slow前一个位置永远碰不到。用生活里的场景类比就很好理解你追前面的人如果速度只比对方快一点点你们迟早会并肩如果你跑得太快反而可能一次次从对方身边冲过去因为你们在同一个位置停留的时间窗口太小。明白了这个前提你就能理解为什么快慢指针入口判断中二次查找阶段两个指针都只走1步。因为这时候要的不是快速追赶而是精确比较两条路径的长度关系速度一致才能保证它们各自走出的距离就是路径本身。顺带提一下实现上的一个常见细节快慢指针的初始位置应该统一从head出发而不是让fast先走一步。很多早期题解喜欢把fast初始化为head.next理由是避免循环条件里多一次判断。这种做法在判环阶段没问题但到了第二次相遇阶段容易产生“差一步”的逻辑混乱面试时也更容易把自己绕进去。从我个人刷题和帮别人复盘的经验看统一起点是最不容易出错的写法推导也最干净。3. 第一次相遇点为什么不是入口D、C、a三段变量的硬核推导现在进入正题为什么第一次相遇之后还需要第二次走位才能找到入口。很多刚开始刷题的同学会有一种直觉既然两个指针相遇了那相遇点是不是就是入口不是。原因在于fast进入环之后可能已经绕了好几圈才追上slow所以第一次相遇点大概率在环内某个随机位置和入口没有固定关系。真正和入口有固定关系的是相遇点继续往前走的一段距离。要证明这一点需要引入三个变量变量含义D从链表头到环入口的步数C环的周长即绕环一圈需要走的步数a慢指针刚入环后继续走到第一次相遇点所用的步数设第一次相遇时慢指针一共走了D a步。快指针速度是慢指针的2倍所以快指针一共走了2 * (D a)步。同时快指针的路径可以拆成三部分从head到入口的D步在环内绕了m圈再从入口沿环走到相遇点的a步。因此得到等式2 * (D a) D m*C a化简D a m*C也就是说慢指针到相遇点为止的总步数恰好是环周长的整数倍。再把式子变形成我们需要的形式D m*C - a (m - 1) * C (C - a)这里的C - a就是“从相遇点继续往前走回到入口还需要多少步”。而D是“从head走到入口需要多少步”。两者差(m - 1) * C正好是整数个环长。这就解释了为什么第二次相遇一定发生在入口让一个指针从head重新出发走D步到达入口另一个指针从相遇点出发走C - a步也能到达入口。由于两条路径的长度只差整数倍环长两者保持相同速度前进必然在入口处第一次相遇。我之前带一个学弟复盘这道题时他卡在“为什么不是相遇点而是入口”这个点上怎么讲都绕不过去。后来我用具体数字模拟了一遍假设D 3,C 5,m 2代入上面的式子他瞬间就明白了。所以如果你也在这个推导上卡过建议拿笔在草稿纸上画一条真实链路把每一步走到的位置标出来效果比空想强很多。这里补充一个极端情况的说明如果环入口恰好就是链表头即D 0此时第一次“运动中的相遇”要等慢指针绕完一整圈才发生。代入等式也能自洽代码里同样不需要特殊分支。第一次推导的时候不需要纠结这种极端情况先掌握常规情形。4. 从推导到代码一次通过的关键细节与本地验证数学推导搞定了代码其实非常短。下面是我推荐的Python实现也是面试时最好写出来的版本class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: slow head fast head # 第一阶段判断是否有环并找到第一次相遇点 while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 第二阶段slow放回头部fast留在相遇点 slow head while slow is not fast: slow slow.next fast fast.next return slow return None如果你想复习Java版本核心逻辑完全一致public class Solution { public ListNode detectCycle(ListNode head) { 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; } }代码短但每个细节都有讲究我逐个说。细节一判断相遇时用is而不是。在Python里is比较的是对象引用匹配链表节点的语义。虽然在理论上也可以工作但如果两个不同节点的val恰好相同用可能误判。这个坑在LeetCode的隐藏用例里出现过别在这种地方丢分。细节二循环条件while fast and fast.next。这个写法同时考虑了空链表和单节点无环两种情况。fast指向None时说明走完了链表没有环fast.next为None说明fast已经站在最后一个节点上同样没有环。细节三第二阶段开始前不需要额外判断slow is fast。因为从数学推导我们知道当入口正好是head时slow置回head后和fast指向同一个节点直接进入循环条件判断发现相等就返回如果入口不是head两者不相等正常进入走位循环。把这一步单独写一个if反而容易混乱。为了让你确认代码真的能跑我给你一段本地验证的脚本。自己构造一个带环链表手动指定入口位置然后调用detectCycledef build_linked_list(values, pos): dummy ListNode(0) cur dummy nodes [] for val in values: cur.next ListNode(val) nodes.append(cur.next) cur cur.next if pos ! -1: cur.next nodes[pos] return dummy.next # 构造链表: 1 - 2 - 3 - 4 - 5 - 3入口是节点3对应values下标2 head build_linked_list([1, 2, 3, 4, 5], 2) solution Solution() entry solution.detectCycle(head) if entry: print(入口节点值:, entry.val) else: print(无环)输出结果应该是入口节点值: 3。你可以把pos改成-1再跑一次应该输出无环。最后聊聊复杂度。这个解法的时间是O(n)因为快指针在环内走的总步数不会超过环长加直线段长度整体是线性的。空间是O(1)只用了两个指针变量。这也是面试官希望看到的答案因为这道题还有另一种哈希表解法遍历链表把每个节点存进集合第一个重复出现的节点就是入口。代码更简单但空间复杂度是O(n)。实际面试中可以先提哈希表法再补充“如果要求O(1)空间可以用快慢指针”这样反而显得你思考全面。5. 面试官顺着这道题还会问什么环长、链表总长与常见变形如果你以为LeetCode-142只是背住代码就完事那说明还没到面试层次。这道题属于那种“写着简单、问起来无止境”的题目我至少被问到过以下几个衍生问题这里一次性整理出来。第一个问题是找到入口之后怎么计算环的长度做法很简单。从入口节点出发用一个指针绕着环走一圈回到入口时走过的步数就是环长C时间复杂度O(n)。更酷一点的做法是在第一次相遇之后让fast停在原处slow继续走同时用一个计数器从0开始累加直到slow重新遇到fast计数器的值就是环长。这个办法不需要事先找到入口只要确认有环就能直接算写起来很简洁。第二个问题是怎么算链表的总长度拆成两段就行——直线段长度加上环长。入口我们已经拿到了从head开始走到入口节点并计数得到D然后按上面方法得到C总长度就是D C。这个派生计算经常作为面试官的追问点考察你能不能灵活组合已经求出的结论。第三个问题是为什么快指针每次走2步而不是3步、4步这个问题我在前面已经讲了一半。速度差为1才能保证追及的连续性速度差大于1时存在“跨过slow而不相遇”的风险虽然某些特定链表下依然能碰巧相遇但算法失去了普适性。面试官问这个问题实际是想确认你理解的是算法本质而不是机械背步骤。第四个问题是这套思路还能用在哪些场景快慢指针本质上是Floyd判圈算法除了判断链表有环还广泛应用于检测函数迭代产生的循环、判断一个序列是否进入重复周期等场景。比如力扣里那道“寻找重复数”的经典题表面是数组问题实际上可以抽象成链表判环来解用的就是这一套原理。如果面试中你主动提到Floyd判圈算法的通用性通常会加分。还有一个小问题也经常被追问第二次循环中如果slow和fast一直不相遇怎么办答案是“不会发生”。数学推导已经证明从head出发的指针和从相遇点出发的指针在到达入口前不可能提前相遇到达入口时必然相遇。所以代码里不需要额外设置终止条件不存在死循环。我自己的经验是这道题完整走完这三步——原理推导、代码实现、衍生问题——才算真正掌握。少一步面试时都可能露怯。如果你正在准备算法面试建议把141和142放在同一天刷先写判环版本再扩展找入口版本形成递进记忆之后再做一道利用快慢指针思想解决非链表问题的题比如寻找重复数把思路彻底迁移出去。最后分享一个我自用的检查习惯每次写完这道题我会用三组用例快速自测——第一组是无环链表期望输出None第二组是入口就在head的链表期望输出head第三组是长直线段加短环的结构比如head走20步才进环、环长只有3用来验证第二次相遇的逻辑不会受D过大的影响。三组用例全部通过代码才算真正过关。刷题这东西AC只是最低标准能经得起追问才是真掌握。
阅读完成 · 觉得有帮助？
