环形链表入环节点怎么找？快慢指针与断链交点法详解

环形链表的入环节点应该是链表类问题里最让新手头疼的一个点。很多人能流畅地说出“快慢指针检测环”但一问到入环节点在哪里就卡住了。这篇文章就聚焦这一件事讲透两种找到入环节点的经典思路一种是用公式证明法直接把快慢指针的路程关系写成等式算出入口的位置另一种是两个链表求第一个相同节点法把环形链表从相遇点拆开变成两条相交链表再用求交集的标准算法定位入口。不管你是准备算法面试还是日常处理链表数据结构这两种思路都值得吃透。1. 问题定位只知道“有环”还不够关键是找到“入口”1.1 环形链表到底在考什么先明确一下问题的样子。链表节点一般长这样一个值value一个next指针。普通链表走到某个节点next是nullptr整个链就结束了。但有些链表某个节点的next会指回前面的节点于是从那个位置开始形成一个环。入环节点就是从head出发第一次“第二次经过”的那个节点。举个例子链表是 1 - 2 - 3 - 4 - 5 - 3那么3就是入环节点。你从head出发走第一次经过3是正常顺序绕一圈回来又碰到3这个3就是环的起点。题目通常要求返回这个节点的指针如果没有环就返回nullptr。这个问题在面试里出现频率很高。它表面上是“判断链表有没有环”但真正的考察点是你不仅要证明有环还要精准定位环的起点。很多人卡就卡在第二步。判断有环可以靠哈希表可以靠快慢指针但找到入环节点需要对指针移动的过程有更深的理解。1.2 为什么相遇点不是入环节点快慢指针判断有环的思路很简单一个指针slow每次走一步一个指针fast每次走两步。如果链表有环fast最终会追上slow两者在某个节点相遇。这个相遇点很多人误以为就是入口其实不是。我举个例子。假设head到入环节点的距离是2步环长是5步入环节点到相遇点的距离是3步。slow从head出发走2步到入口再走3步总共走了5步到达相遇点。fast同时出发速度是slow的两倍走了10步相当于从head走2步进入环然后在环里走了8步也就是绕了一圈加3步最终也在相遇点。这个相遇点离入口还有2步的距离它显然不是入口。所以问题就来了已知相遇点怎么算出入口这时候就需要真正的“算法”出场而不是继续靠感觉。这也是为什么我一再强调光会写快慢指针的循环不够必须理解相遇点和入口之间那个隐藏的数学关系。1.3 两条解题路线一个共同起点针对“从相遇点找入口”这件事经典的解法主要有两条路线。第一条是公式证明法。它把快慢指针的路程写成两个等式然后通过代数变换直接推出“从head出发的指针”和“从相遇点出发的指针”会同时走到入环节点。这个方法的优点是代码极简只需要在找到相遇点之后再写一个while循环。缺点是推导过程需要理解变量含义尤其是那个多绕的“圈数n”很多人就是在这里被绕晕。第二条是两个链表求第一个相同节点法。它在相遇点把链表断开环形结构立刻变成两条相交的普通链表入环节点恰好是这两条链表的第一个公共节点。然后直接套用“求两个链表交点”的经典算法。这个方法不需要复杂的代数推导但对链表结构变化的想象力要求更高。两条路线的共同起点都是先让快慢指针找到相遇点。所以这篇文章会先把这个基础写透再分别展开两条路线最后聊聊实操里的坑和选型建议。2. 公式证明法从快慢指针相遇点到入环节点的数学推导2.1 快慢指针为什么会相遇在推导公式之前先回答一个基础问题快慢指针在环里一定能相遇吗答案是肯定的前提是快指针每次走2步慢指针每次走1步。可以类比两个人在环形操场跑步。一个跑得快一个跑得慢只要跑道是有限的跑得快的人最终会从后面追上跑得慢的人。在链表环里也一样。数学上更严谨一点当慢指针刚进入环的时候快指针已经在环里某个位置了。快指针相对慢指针的速度是每移动一次多跑1个节点距离也就是每秒接近1个节点。环的长度是有限的所以快指针不会跳过慢指针而是会在有限步内贴上去。这里有一个细节值得注意从慢指针进入环到被追上慢指针在环内走的距离不会超过一圈。理由很简单快指针相对慢指针是每轮接近一步而两者在环内的初始距离最多就是环长减一所以在慢指针还没绕满一圈的时候快的就已经追上了。ListNode* getMeetNode(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { return slow; } } return nullptr; }这段代码就是标准的快慢指针。注意循环条件是fast和fast-next都不为空否则说明链表无环。一旦slow和fast相等说明有环并且当前节点就是相遇点。2.2 公式推导全过程现在开始推公式。先把变量定义清楚这一步非常关键变量定义一旦含糊后面就全乱了。设a 表示从head出发走多少步能到达入环节点L 表示环的长度也就是在环里走L步会回到原点b 表示从入环节点出发沿next方向走多少步能到达快慢指针的相遇点c 表示从相遇点出发沿next方向走多少步能回到入环节点。根据环的定义b c L。接下来看路程。slow指针从head出发走到相遇点一共走了 a b 步。fast指针从head出发走到相遇点除了走完 a b 步之外比slow多绕了 n 圈整环其中 n 是正整数至少为1。所以fast走的路程是a b nL因为fast的速度是slow的二倍所以相同时间内fast的路程等于slow路程的二倍。于是得到等式2(a b) a b nL这个等式两边同时减去 a b得到a b nL到这里先停一下感受一下这个结论的含义。它说明head到相遇点的距离恰好是环长的整数倍。换句话说如果你从head出发走到相遇点全程所需步数正好可以拆成若干个完整环。这个结论本身已经很漂亮但更漂亮的是下一步。继续化简。因为 b c L所以 b L - c。把 b 代入 a b nLa nL - b a nL - (L - c) a (n - 1)L c这个式子的意义非常直观从head走到入环节点需要a步而从相遇点走到入环节点需要c步。a和c之间差的是 (n - 1) 个整环。所以我们可以这样操作把一个指针p放在head一个指针q放在相遇点。然后两个指针每次都走1步。当p走了a步正好到达入环节点q走了c步也到达入环节点就算q多绕了n-1圈最终还是在入环节点。它们必然会在入环节点相遇。这就是公式证明法的核心。记住一句话方便面试时说出来从head到入口的距离等于从相遇点到入口的距离加上若干个整环。2.3 代码实现与边界处理公式推导完代码就水到渠成了。ListNode* detectCycle(ListNode* head) { ListNode* fast head; ListNode* slow head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { break; } } if (!fast || !fast-next) { return nullptr; } ListNode* p head; ListNode* q slow; while (p ! q) { p p-next; q q-next; } return p; }这里有几个容易踩的细节。第一个是循环跳出后判断无环的方式。break退出时可能是找到了相遇点也可能是快指针已经走到了nullptr。所以要检查fast和fast-next是否为空只要有一个为空就说明链表没有环直接返回nullptr。第二个是第二个while循环的终止条件。因为我们已经知道链表有环所以p和q最终一定会相遇这个循环不会死循环。如果写的时候没有先判断无环这里就可能出问题。第三个是快慢指针初始位置的写法。这里用的是slow headfast head然后在循环体里先移动再比较。如果你把初始值设为fast head-next循环条件也要相应调整两种写法都对但别混着用。2.4 用一个例子验证公式光看公式还不够我建议你拿一个具体例子手动走一遍。假设链表是 1 - 2 - 3 - 4 - 5 - 6其中6的next指向3。那么入环节点是3环长L 4节点3、4、5、6。head到入口的距离a 2走两步从1经过2到达3。假设快慢指针在节点5相遇那么从入口3到节点5沿next方向走b 2步。c L - b 2。slow的路程是a b 4步fast的路程是8步正好是slow的两倍并且fast在环里多绕了n 1圈。根据公式a c确实是2 2。然后p从head出发q从相遇点5出发都走一步。p走2步1 - 2 - 3q走2步5 - 6 - 3。两者在3相遇返回3正确。你可以把b改成3也就是相遇点在6再验证一遍。此时c 1a还是2等式是2 (n-1)L 1当n1时成立结果依然是3。验证完你会对公式有更深的信任。3. 两个链表求第一个相同节点法断环成链把环问题转化为交点问题3.1 在相遇点断开为什么形成两条相交链表公式证明法是纯代数思路很多人觉得跳跃。如果你更习惯“看得见摸得着”的变换那就要看第二个方法把环形链表从相遇点剪断变成两条链表然后求交点。回到之前定义的变量。设快慢指针在节点M相遇。M的next指向环里的下一个节点我们把M-next保存为N然后把M-next置为nullptr。这个操作相当于在M处把环剪开。剪开之后链表变成了两条第一条链表从head出发经过入环节点P最终到达M第二条链表从N出发沿着原来的环走一圈经过入环节点P最终也到达M。因为M-next已经变成nullptr所以M是这条链表的终点。两条链表从P节点开始共享一段节点一直到M节点结束。也就是说P是这两条链表的第一个公共节点而P正是我们要求的入环节点。反过来想如果不剪断这两条链表根本不存在剪断之后环结构就“展平”成了一个Y字形的相交结构入口就是Y字的分岔点。为什么要找“第一个”公共节点而不是随便一个公共节点因为两条链表可能共享多个节点比如P、4、5、M都是公共节点但只有P才是入环节点。A链表在P之前是纯粹的环外节点和B链表没有任何交集所以第一个相遇的节点一定是P。这一点理解清楚求交点算法的指向就明确了。3.2 用“求两个链表交点”的标准算法求解求两条链表的第一个公共节点是一个独立的经典问题解法很成熟。最直观的做法是“对齐法”。先分别遍历两条链表求出长度lenA和lenB。让较长链表的指针先走长度差步这样两个指针离各自链表尾部的距离就一样了。接下来两个指针同时一步一步走第一次指向同一个节点时这个节点就是交点。ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { int lenA 0, lenB 0; ListNode* p headA; ListNode* q headB; while (p) { lenA; p p-next; } while (q) { lenB; q q-next; } p headA; q headB; if (lenA lenB) { int diff lenA - lenB; while (diff--) p p-next; } else { int diff lenB - lenA; while (diff--) q q-next; } while (p ! q) { p p-next; q q-next; } return p; }求交点还有一个更简练的双指针写法两个指针分别从两条链表头出发每次走一步走到末尾后跳到对方链表的头部继续走。因为两个指针走过的总路程最终相等它们一定会在第一个公共节点相遇。这个写法不需要求长度代码短但理解起来稍微绕一点。如果你在面试中写这版记得说清楚它的原理否则面试官会觉得你在背代码。3.3 求入环节点的完整流程把上面的方法组合起来流程就是三步。第一步用快慢指针找到相遇点M。如果快指针走到nullptr说明没有环直接返回nullptr。第二步保存N M-next然后执行M-next nullptr把环断开。这时得到两条链表head到MN到M。第三步调用getIntersectionNode(head, N)得到交点这个交点就是入环节点。找到之后记得恢复现场把M-next重新指向N。如果忘了恢复原来链表的结构就被永久破坏了后续再遍历就会出问题。为什么入环节点一定是两条链表的交点这一点前面已经解释过。你可能会问两链表在M节点也是公共节点为什么返回值不是M而是P原因是求交点算法按“第一个公共节点”返回也就是从两条链表的头同时往后扫第一次相等的位置。显然在P之前两者都不相等所以返回的是P。3.4 两种方法到底有什么区别从结果来看公式证明法和断链法最终都返回入环节点时间复杂度都是O(n)空间复杂度都是O(1)。但两者的思维路径不同。公式证明法的整个过程都在原链表上操作不需要修改指针代码非常短。它需要你接受那个代数推导一旦接受后续就是在背结论从head和相遇点同时走相遇点就是入口。断链法需要一次指针修改和一次恢复代码长一些但背后的逻辑非常“工程化”把一个陌生问题转化成熟知问题。环形链表不熟悉但两条链表求交点你总会吧这种“转化为已解决问题”的思路在工程里非常常用。我个人建议你两个都掌握因为面试官可能会追问“还有没有其他解法”。能把两种解法讲清楚说明你不是只会背模板而是真的理解了链表的结构。4. 实操过程与核心代码实现4.1 构造带环链表的测试数据纸上谈兵再多不如自己跑一遍代码。但链表带环直接定义一个数组再串起来会比较麻烦。这里我写一个辅助函数根据数组和pos参数构建一条带头部环的链表。ListNode* createListWithCycle(const vectorint vals, int pos) { if (vals.empty()) return nullptr; ListNode* dummy new ListNode(0); ListNode* tail dummy; ListNode* cycleNode nullptr; for (int i 0; i (int)vals.size(); i) { ListNode* node new ListNode(vals[i]); tail-next node; tail node; if (i pos) { cycleNode node; } } if (cycleNode) { tail-next cycleNode; } return dummy-next; }这个函数的逻辑很直白遍历数组成链表同时记录第pos个节点。全部串完之后让最后一个节点的next指向第pos个节点环就形成了。如果pos等于-1cycleNode保持nullptr生成的链表就是普通链表。测试数据的结构要清楚。比如vals {1, 2, 3, 4, 5, 6}pos 2那么形成的链表就是1 - 2 - 3 - 4 - 5 - 6 - 3入环节点是节点3。4.2 整合两种解法跑一个完整demo我习惯把两种解法放在同一个文件里共用同一个快慢指针找相遇点的函数然后分开验证结果。这样能直观看到两种算法的输出一致性。#include iostream #include vector using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* getMeetNode(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return slow; } return nullptr; } ListNode* detectCycleFormula(ListNode* head) { ListNode* meet getMeetNode(head); if (!meet) return nullptr; ListNode* p head; while (p ! meet) { p p-next; meet meet-next; } return p; } ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { int lenA 0, lenB 0; ListNode* p headA; ListNode* q headB; while (p) { lenA; p p-next; } while (q) { lenB; q q-next; } p headA; q headB; int diff lenA - lenB; if (diff 0) { while (diff--) p p-next; } else { diff -diff; while (diff--) q q-next; } while (p ! q) { p p-next; q q-next; } return p; } ListNode* detectCycleIntersect(ListNode* head) { ListNode* meet getMeetNode(head); if (!meet) return nullptr; ListNode* nxt meet-next; meet-next nullptr; ListNode* entry getIntersectionNode(head, nxt); meet-next nxt; return entry; } int main() { vectorint vals {1, 2, 3, 4, 5, 6}; int pos 2; ListNode* list1 createListWithCycle(vals, pos); ListNode* entry1 detectCycleFormula(list1); cout formula method: entry1-val endl; ListNode* list2 createListWithCycle(vals, pos); ListNode* entry2 detectCycleIntersect(list2); cout intersect method: entry2-val endl; return 0; }输出结果应该都是3。跑一遍你会发现两种方法返回同一个节点互相作为验证。我一直觉得能用两个独立的方法跑同一个测试用例是最让人放心的验证方式。4.3 释放链表内存时的一个坑带环链表删除时不能简单遍历delete因为环里的节点会被重复访问可能造成重复释放或内存泄漏。正确做法是先把环断开比如找到入环节点再让尾节点的next等于nullptr恢复成普通链表然后正常delete。在算法题刷题场景里内存释放往往不是重点但在实际项目里写链表工具类时这就是基本功了。我自己曾经因为忘记断开环在delete时程序直接崩溃后来在代码注释里特意标了一句有环先断环再释放。习惯成自然之后再也没有踩过这个坑。5. 常见问题与排查技巧实录5.1 快指针为什么不能一次走3步或4步这是一个高频追问。快指针不是走得越快越好。fast每次走2步相对slow的速度是每轮接近1步这就保证了只要环存在它不可能“跳过”slow必然会在有限次内追上。如果fast改成每次走3步相对速度变成2步。考虑环长为2的特殊情况比如环里只有两个节点fast在某个节点slow在前一个节点两者相对距离是1。fast每轮前进3步slow前进1步相对位置变化为2恰好是环长2的整数倍于是fast永远在slow同样的相对距离上永远追不上。步长越大的情况越容易出现这种“恰好跳过”的组合。所以标准解法固定为fast走2步不是随意选的而是这个速度能保证相遇的充要条件在数学上最简单。5.2 快慢指针初始位置的两种写法最常见的写法是slow headfast head然后循环体里先移动再判断。这个写法需要注意因为一开始slow fast如果你先比较再移动第一次比较就会误判成“已经相遇”。另一个写法是slow headfast head-next这样初始就不相等循环条件也要相应改成while (fast fast-next)移动方式变成slow slow-nextfast fast-next-next。这个写法在某些语言的某些实现里能省一次循环但逻辑上大同小异。面试时我推荐用第一种也就是先移动再比较。因为它更贴近“从同一起点出发”的直觉后面公式推导时也容易对应。写代码时只要记住顺序就行。5.3 断链法忘了恢复现场怎么办断链法里M-next被临时改成nullptr。如果函数返回之前忘记恢复调用方再遍历链表会从M处断掉整个链表就坏了。而且这个bug很隐蔽如果没有立即用链表可能过很久才暴露。我的习惯是“先保存后修改再恢复”三步走。保存N修改M-next用完立刻恢复。如果你用语言执行环境有任何异常处理机制尽量把恢复操作放在finally里或者用RAII管理。总之恢复现场要当成代码的一部分而不是可选的善后。如果只想要入环节点其实可以不物理修改指针而是用逻辑上“当成两条链表”的方式用双指针换路法求交点。这个方法不需要M-next为nullptr也能跑通吗不行换路法依赖指针走到nullptr来切换链表所以还是得物理断开。这也是为什么我强调恢复现场。5.4 节点值重复会导致结果错误吗会。如果你写判断条件是if (p-val q-val)那就完全错了。链表里节点的值可能重复比如入环节点的值是5后面某个节点的值也是5按值判断就会返回错误节点。正确做法永远是判断节点地址是否相等也就是p q。这个比较的是指针不是值。面试里如果链表有重复值按值判断是必炸的。刷题时要养成习惯比较链表节点一律用指针相等。5.5 无环链表的处理顺序不能颠倒很多人写detectCycle时先调用getMeetNode如果返回nullptr就返回nullptr。这一步没问题。问题是在断链法中如果忘掉这一步直接对无环链表取M-next会访问空指针直接崩溃。所以在组合方法时顺序必须是先找相遇点确认有环再断开操作。这也是一个面试官爱挖的坑代码里提前判断无环能体现你考虑边界条件的习惯。5.6 环入口就在head本身或者链表只有一个节点链表只有一个节点并且next指向自己那么head就是入环节点。快慢指针从head出发slow走一步回到headfast走两步也回到head相遇点就是head。公式法中p从一开始就是headq也是head循环不执行直接返回head正确。断链法也成立相遇点M是headNhead-next断开后两条链表分别是head和头节点的next节点它们的第一个公共节点还是head。这个边界用例比较极端手动测一次能帮你确认自己的实现没有特判漏洞。6. 复杂度对比与应用场景选型建议6.1 三种思路的横向对比把常用的几种解法放在一起看会更清楚它们的差异。解法时间复杂度空间复杂度是否修改链表代码复杂度理解难度哈希集合O(n)O(n)否低低公式证明法O(n)O(1)否低中断链交点法O(n)O(1)是临时断开中中哈希集合的思路最简单遍历链表把每个节点地址存进set第一个重复的节点就是入口。因为入环节点是第一次被访问两次的节点所以这个逻辑天然正确。缺点是空间复杂度是O(n)面试里通常不会说它是最优解但作为思路补充很好。公式证明法和断链交点法都达到O(1)空间区别在于是否临时修改链表。公式法完全只读适合那些链表被多个地方引用的场景你改指针可能会影响别人。断链法需要改指针再恢复恢复不及时就出问题所以工程上更谨慎。6.2 面试选哪种工程选哪种面试场景我建议先讲公式证明法。因为它代码短现场不容易写错推导也只需要三步列等式、化简、得出结论。面试官能顺着你的推导走比看一段“断链恢复”的代码轻松。如果面试官追问“有没有别的思路”再把断链交点法抛出来。这时候体现的是知识面和转化能力。你可以说“快慢指针找到相遇点后把相遇点断开环就变成两条相交链表入环节点就是第一个交点。”这句话一说面试官基本就能判断你对链表结构很熟。工程场景我会更谨慎。如果只是判断一个数据结构有没有环公式法是最合适的因为不改变链表结构。断链法虽然也能恢复但万一恢复逻辑被并发调用打断链表状态就不可控了。链表本身往往承载业务数据破坏结构的结果比算错一个返回值严重得多。6.3 快慢指针的思想还能延伸到哪些场景入环节点只是快慢指针的一个应用。这个“一快一慢”的模型在链表和数组问题里能解决很多事情。第一个是找链表中间节点。slow每次走一步fast每次走两步fast到末尾时slow正好在中点。这个技巧在归并排序、回文链表判断里都用得上。第二个是判断回文链表。先用快慢指针找到中点再把后半部分反转然后从头逐个比较。不需要额外空间时间复杂度也是O(n)。这是链表题里比较综合的一道题很推荐练手。第三个是寻找重复数。给定一个数组某些情况下可以用快慢指针模拟链表中的环定位重复元素。虽然数组下标跳转和链表指针不同但底层思想是相通的把状态转移看成一条链环的入口就是答案。理解了这些延伸你会发现“快慢指针”不是一个孤立的模板而是一种从速度差异里提取信息的思维方式。写在最后的实操体会两组方法刷过之后我自己有一个很深的体会环形链表找入口最忌讳的是不看图死磕代码。第一次学习时我直接对着代码一行行读读了半小时都没想明白为什么第二个while能停在入口。后来我拿出一张纸画了一条带环的链表标出a、b、c手动走了一遍slow和fast等式一下就通了。所以如果你正卡在这个问题上我的建议是先画图再标变量最后写代码。不要一上来就背结论。第二公式法和断链法不要只学一个两个都写一遍再用我文章里的测试数据跑一下输出你会对“入环节点”这个位置建立起非常扎实的直觉。以后再遇到变种题比如寻找重复数、判断回文链表你也能更快认出它们底层的相似结构。最后再分享一个小技巧面试手写这类题时变量名尽量用a、b、c这样有明确含义的记号或者写成aHead到entry的距离、meet到entry的距离写代码时注释标清楚。这样即使你推导过程中有一点紧张面试官也能跟着你的思路走而不是看一个冷冰冰的while循环猜你懂不懂原理。