力扣142这道题我刷了三轮才觉得自己真正吃透了它。第一轮用哈希表秒过觉得不过如此第二轮被面试官追问能不能O(1)空间当场卡壳第三轮才静下心把快慢指针的数学推导彻底推了一遍。回头再看这道题之所以被捧为链表题里的常青树是因为它从判环到找入口硬生生拔高了一档难度考察的不只是会不会双指针而是能不能把一个看似玄学的相遇点用手推公式还原出背后的几何关系。这篇文章不聊虚的直接拆解这道题的核心思路、数学证明、实现细节以及那些文档里不会写但你大概率会踩的坑。1. 题目分析与核心思路拆解1.1 问题本质判环之后的定位才是真正的考点力扣上第141题是判断链表是否有环第142题在它基础上多问了一句如果有环返回环的入口节点。这一问难度就上了一个台阶。141题你只需要回答有没有快慢指针相遇就说明有环不欢而散即可142题要求你精确指出环从哪里开始这需要的不只是检测能力还有对链表结构和指针路程关系的深层理解。很多第一次刷这道题的人会有一个直觉我遍历链表每经过一个节点就存进哈希集合如果第一次遇到一个已经在集合里的节点那这个节点不就是入口吗没错这个思路完全正确而且非常好写。但它有一个致命的短板——空间复杂度是O(n)。面试官看到你用了哈希表大概率会追问一句能不能不用额外空间这句话一出才是142题真正的考场。顺带说一句我知道有些同学会尝试用值相等来判断重复节点。这在大二数据结构作业里没问题但在力扣这种正式环境下是个坑链表节点的值可能是重复的两个不同的节点完全可能拥有相同的val。你需要比较的是节点的引用或者说对象身份而不是值。哈希表解法里存的是节点对象本身这点没问题但如果你自己写比较逻辑千万别搞错对象。1.2 为什么哈希表解法不是最优解哈希表解法本身是一种暴力但不笨的解法它在很多实际工程场景里甚至是首选方案。但在算法面试的语境下我们需要追求的是最优解。142题的标准最优解就是Floyd判圈算法也叫龟兔赛跑算法的变体核心思路是快慢双指针空间复杂度压到O(1)。为什么O(1)空间这么重要链表本身就是一种对空间敏感的结构。一个链表可能有十万、百万个节点如果用哈希表记录每个节点的引用内存占用随链表长度线性增长。而双指针方案自始至终只占用两个指针变量无论链表多长额外空间就是常数级别。在实际工程里处理链表、图、依赖关系时这种空间上的克制往往就是能不能扛住大数据的分水岭。我第一次面试时面试官听我说了哈希表方案后点头说正确然后补了一句假设这个链表非常长有几千万个节点你的方案内存还够吗我当场就意识到正确不是终点高效才是。2. 快慢指针原理与数学证明2.1 Floyd判圈算法的直观理解龟兔赛跑快慢指针的思路用一句话说就是让两个指针同时从链表头部出发慢指针每次走一步快指针每次走两步。如果链表有环快指针最终会追上慢指针不是超过而是相遇如果链表没环快指针会先走到末尾。你可以把这个过程想象成两个人在圆形操场上跑步一个人速度快一个人速度慢只要跑道是封闭的有环速度快的那个人迟早会从后面追上速度慢的那个人。而如果跑道有一个笔直的入口段链表头到环入口的非环部分那么快慢指针一定是在进入环之后才相遇的——因为在直道部分快指针永远领先且不存在追及的问题。很多人会问快指针的速度为什么是慢指针的2倍而不是3倍、5倍这背后有一个关键原因快指针走2步、慢指针走1步时二者的相对速度恰好是1步/轮。也就是说在环内每经过一轮快指针相对慢指针靠近一步不会跳过慢指针所在的节点。如果快指针走3步、慢指针走2步相对速度是1步也可以但如果快指针走3步、慢指针走1步相对速度是2步理论上存在跳过慢指针而不在同一节点相遇的可能性。为了数学上的简洁和逻辑上的严谨选择快2慢1是最稳妥的方案。2.2 数学推导为什么第二次相遇点就是入口这部分是142题的精髓也是面试时最能跟面试官battle的地方。我们需要用到路程关系来推导入口位置。设链表头到环入口的距离为 a边的数量环入口到首次相遇点的距离为 b首次相遇点继续前进回到环入口的距离为 c环的总长度为 L b c。在快慢指针第一次相遇时慢指针一共走了 s a b 条边它从head走到入口再从入口走到相遇点。快指针走了多少它走了 f a b nL其中 n 是快指针在环内多绕的圈数n ≥ 1因为快指针速度是慢指针2倍它一定比慢指针多走至少一圈否则不可能追上慢指针——这里我稍微解释一下假设快指针和慢指针都进入环后快指针一开始在慢指针前方由于快指针快它会从后方再次追上来这个过程它必然比慢指针多走了至少一整圈。因为快指针速度是慢指针的2倍所以 f 2s代入上面两个式子a b nL 2(a b)整理得a nL - b n(b c) - b (n-1)(b c) c (n-1)L c这个式子意味着什么它告诉我们从相遇点出发往前继续走 c 条边就到达环入口而从链表头出发往前走上 a 条边也正好到达环入口。由于 a (n-1)L c等号的左边是从链表头到入口的路径长度右边是从相遇点出发绕若干圈可能0圈之后回到入口的路径长度。所以算法第二阶段就呼之欲出了第一次相遇后让一个指针回到链表头另一个指针停在相遇点然后两个指针每次各走一步。它们会在某个时刻相遇而相遇的那个节点就是环的入口。为了让你彻底信服我手动模拟一个例子。设链表为节点1 → 节点2 → 节点3 → 节点4 → 节点5 → 节点6 → 节点4入口是节点4因为节点6又指回节点4。这个链表非环部分 a 3节点1到4有3条边环部分 L 34→5→6→4。从head出发第1轮slow到节点2fast到节点3第2轮slow到节点3fast到节点5第3轮slow到节点4fast到节点4相遇入口节点4恰好也是相遇点。用一个更典型的例子节点1 → 节点2 → 节点3 → 节点4 → 节点5 → 节点6 → 节点7 → 节点5入口是节点5。非环部分 a 4环部分 L 35→6→7→5。模拟第1轮slow到2fast到3第2轮slow到3fast到5进入环第3轮slow到4fast到7第4轮slow到5fast到6第5轮slow到6fast到5第6轮slow到7fast到7相遇相遇点在节点7。按公式算a 4L 3b 入口5到相遇节点7的距离 2c 相遇点7回到入口5的距离 17→5。n 第一圈相遇到所以 a c (n-1)L 1 0 1这不对。等一下我们重新算 n。好这里要注意 n 表示快指针在相遇时比慢指针多绕的完整圈数。回到刚才的例子慢指针从入口5走到相遇点7走了 b 2 条边快指针在相同时间内从入口5附近出发多走了至少一整圈。慢指针总路程 s a b 6快指针 f 2s 12。快指针实际路程 非环段4 环内多走的路径。环内路径12 - 4 8而环长38 2圈 2条边所以 n完整圈数 2。公式 a (n-1)L c (2-1)*3 1 4。正确这就说明n 不一定是1具体取决于非环部分长度和环长度的比值。公式神奇的地方就在于不管 n 是多少最后总能化简成从相遇点走 c 步到入口和从头走 a 步到入口是同一个节点。这个结论跟 n 无关才是整个算法最漂亮的部分。3. 完整实现与踩坑实录3.1 代码实现Python版与关键边界条件这道题的主流语言实现差异不大我直接用Python写一版带详细注释的class ListNode: def __init__(self, x): self.val x self.next None def detectCycle(head: ListNode) - ListNode: # 空链表或只有一个节点且无环的链表直接返回None if not head or not head.next: return None slow, fast head, head # 第一阶段寻找快慢指针的相遇点 # 注意循环条件是 fast 和 fast.next 都不为空 # 如果链表中无环fast 会先到达链表末尾 while fast and fast.next: slow slow.next fast fast.next.next if slow fast: break else: # 循环正常结束说明 fast 走到了末尾无环 return None # 第二阶段入口定位 # 一个指针从 head 出发另一个从相遇点出发都每次走一步 ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptr这段代码里有两个细节值得注意。第一第一阶段循环结束后需要判断是否真的找到了相遇点。这里我用的是Python的while...else语法——如果循环是因为条件不满足fast或fast.next为空而正常退出就执行else分支返回None如果是因为break退出找到相遇点则跳过else。如果你用的语言不支持这种语法就需要在循环后加一个判断if not fast or not fast.next: return None确保没环的情况下不会进入第二阶段。第二第二阶段为什么能保证ptr和slow一定在入口相遇前面已经证明了从head到入口的距离等于从相遇点继续走到入口的距离可能多绕几圈但殊途同归。所以两个指针以相同速度前进必在入口处会合。用Java写的话核心逻辑一致但要注意Java的循环跳出处理public ListNode detectCycle(ListNode head) { if (head null || head.next null) return null; ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { // 找到相遇点跳出循环 break; } } // 无环判断 if (fast null || fast.next null) return null; ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; }注意Java版本的边界判断必须放在循环之后、第二阶段之前。为什么这么写因为跳出循环有两种可能一是break有环二是循环条件不满足无环。如果没有环fast一定先到null此时fast是空指针。如果你直接开始第二阶段slow和ptr永远不会相遇或者更糟提前抛异常所以必须先排除无环的情况。3.2 边界条件与常见实现错误我在刷题群里看到过不少同学在这道题上栽跟头典型的错误场景有这几个错误一循环条件写成while fast.next ! None。这个写法在无环链表上会直接抛空指针异常——因为fast已经走到null了你还去访问fast.next。正确姿势是while fast and fast.next同时检查当前节点和下一个节点。错误二忽略整条链表就是一个环的退化情况。如果head本身就在环上比如最后一个节点指向头节点那么第一次相遇时相遇点可能恰好就是头节点本身。此时第二阶段让ptr headslow留在相遇点也就是head两者一开始就相等循环直接跳过返回head。这个行为是正确的但有同学会怀疑指针都没动怎么就返回了答案是头节点就是入口逻辑上完全没问题。错误三在第二阶段用不同步长。我见过有人写成ptr每次走一步slow每次走两步——结果怎么都等不到相遇程序死循环。第二阶段必须两个指针都走一步因为它们是在对向逼近入口速度一致才能保证同时到达。错误四初始化指针位置不同。有些题解把slow和fast初始化为head和head.next这样可以减少一次循环迭代但会导致数学推导中的距离定义变化第二阶段的计算也得跟着调整。我不建议新手用这种优化因为它让公式变得不直观调试起来更费劲。老老实实从head一起出发逻辑最干净。错误五把判断无环放在找到相遇点之前。这听着有点绕实际操作中就是在循环内一旦slow fast就break但如果你在break之前先判断了fast None此时fast明明还在合法位置反而会误判成无环。理清顺序先找相遇再判断无环循环结束后的状态最后第二阶段。4. 衍生问题与面试官追问4.1 变体与扩展环的长度、链表相交与循环依赖检测142题解决之后很多相关的变体问题也顺手能化。比如如何求环的长度在第一次相遇后让其中一个指针原地不动另一个指针继续走边走边计数等再次相遇时走过的步数就是环的周长。这个操作本质上是在绕环一圈因为快指针或者慢指针取决于你让谁走从相遇点出发沿着环走一圈必然回到相遇点。再比如判断两个链表是否相交的经典题目它的一个高赞解法就是把其中一个链表的尾节点接到另一个链表的头节点上如果新链表有环说明两个原链表相交而且环的入口就是相交节点。这个解法正好用到了142题的能力属于把A题的解法移植到B题的典型套路。在实际工程项目里判环和找环入口的能力远不止刷题这么简单。我在某个外包项目里处理过模块间循环依赖的问题十几个模块互相引用配置里看不出来但启动时直接栈溢出。我写了个脚本把所有模块依赖关系抽象成链表用快慢指针定位循环依赖的入口模块五分钟就揪出了问题源头。这个思路在包管理器、构建工具、数据库外键约束、甚至JVM内存泄漏分析里都有应用场景。快慢指针是判断引用链成环的最轻盈的手段没有之一。4.2 复杂度分析与面试表达要点先给出这道题的标准复杂度时间复杂度O(n)空间复杂度O(1)。时间复杂度的解释要稍微讲究一下。第一阶段慢指针最多走a b条边快指针走2(a b)条边由于a b ≤ nn为链表总节点数所以这一阶段是O(n)。第二阶段两个指针各自最多再走a条边而a ≤ n所以也是O(n)。总时间复杂度O(n)。这里有个小细节有些同学担心快指针在环里绕了n圈会不会超时其实不会因为快指针的总路程是慢指针的2倍而慢指针走完整个链表都不到n条边快指针再怎么绕也是2n的量级依然是线性。空间复杂度的解释就简单了全程只用了slow、fast、ptr三个指针变量没有额外数据结构所以O(1)。面试怎么表达能拿高分我个人建议按照暴力解 → 优化解 → 数学证明 → 代码实现的顺序组织语言。先说哈希表解法能过但空间O(n)自然引出面试官你有没有想过O(1)空间的解法然后讲快慢指针的相遇逻辑接着用2.2节那个推导公式证明入口定位的正确性最后再写代码。这个过程就像搭积木一层层垒上去面试官想打断你都插不上话。还有个隐藏加分项主动说明为什么不选择哈希表。别等面试官问自己先说哈希表方案时间复杂度O(n)、空间O(n)当链表规模很大时空开销不可接受然后话锋一转所以我们需要用双指针把空间压到O(1)。这种先踩一脚次优解再给出最优解的讲法会让你的答案显得有层次。4.3 快指针步长换成3行不行面试官还可能追问一个变体如果把快指针步长改成3算法还成立吗这个问题的标准答案是不一定保证成立。原因是当快指针每次走3步、慢指针每次走1步时二者相对速度是2步/轮快指针可能直接从慢指针头顶跳过去导致二者永远不在同一节点相遇尽管它们可能在环内错位游走。严格来说在某些环长和特定位置组合下步长3也能相遇但无法保证所有情况都能相遇。而步长2在任意环状结构下都能保证相遇因为相对速度是1步/轮追击过程不会越位。这个讨论同样可以延伸到快指针每次走2步、慢指针每次走1步为什么是刚刚好的选择既保证相遇又减少循环轮数。如果快慢指针步长差是1那么快指针相对慢指针每轮靠近1条边环长L无论多大最多L轮就能追上如果步长差是2最坏情况下可能要重复多次才能相遇而且存在跳过的风险。所以要我总结快2慢1不只是惯例背后是保证相遇 效率最优的双重选择。5. 我在实际使用中总结的几点心得最后分享几个只有自己动手推过、跑过、调试过才能体会到的东西。第一个心得是数学推导一定要自己手推一遍不要只看题解里的公式。我第一次看题解推导的时候觉得懂了但面试时被问为什么相遇后一个指针从头走一个从相遇点走就能碰到入口我愣了好几秒因为那层n可能大于1的理解是模糊的。后来我自己在纸上把a5、L3的例子手动模拟了一遍真正看到了快指针绕了两圈才追上慢指针的过程才彻底明白公式里那个(n-1)L是怎么回事。从那以后我再也不怵这道题了。第二个心得是遇到双指针追及类的问题可以画图。我见过不少同学在脑子里硬想绕来绕去把自己绕晕。我的习惯是拿一张草稿纸把链表画成一排方框快慢指针用两个不同颜色的小箭头标出来每走一轮就更新箭头位置。有时候你眼睛看到哦它们在这里相遇了比你推十行公式都深刻。第三个心得是刷题要有联合作战意识。142题可以跟141题判环、160题相交链表、287题寻找重复数放在一起刷它们要么是同一个Floyd算法的变体要么能用同一个快慢指针的思维模型去解。把这几道题放一起琢磨你会体会到一种套路解决多道题的快感这才是算法训练真正值钱的地方。第四个心得是实际工程代码不要照搬力扣的函数签名。力扣题解里detectCycle返回一个节点但真实项目里你往往需要的是这个循环依赖的入口是什么模块这个引用环有多长环里都有哪些节点。我一般会在做题解法的基础上封装成CycleResult类带上hasCycle、entryNode、cycleLength三个字段一次遍历全拿到。这种从题目到工程的转化能力才是面试官真正想从你身上看到的东西。说到底力扣142这道题代码不过三十行但背后是数学、空间复杂度的权衡、边界条件的考量和工程思路的迁移。把它啃透你得到的绝不只是会做一道题而是一整套处理链状结构中环问题的思维方式。