LeetCode LCR 022. 环形链表 II：返回链表开始入环的第一个节点-程序员充电站

LCR 022. 环形链表 II：返回链表开始入环的第一个节点 🚀

在链表类算法中，环形链表相关题目绝对是面试高频考点！从基础的“判断链表是否有环”，到进阶的“找到入环第一个节点”，层层递进的考察方式能很好地检验我们对链表结构和双指针技巧的理解。今天就来深度拆解 LCR 022. 环形链表 II，带你从原理到代码，彻底搞懂这道经典题～

一、回顾昨日算法题：环形链表：判断链表是否有环的核心逻辑 💡

在解决“找入环节点”之前，我们先回顾它的基础题——“判断链表是否有环”。这道题的核心解法是快慢指针法，思路特别形象：

定义两个指针fast（快指针）和slow（慢指针），同时从链表头head出发；
fast每次走 2 步，slow每次走 1 步，就像两个人在环形跑道上跑步，速度不同；
如果链表没有环，fast会先跑到链表末尾（遇到null），此时直接返回无环；
如果链表有环，slow进入环后就会一直在环内循环，而fast会在环内追上slow（相当于套圈），此时就能确定链表有环。

代码亮个相：

function hasCycle(head) { let slow = head; let fast = head; while(fast && fast.next) { // 快指针先到尾部 slow = slow.next; fast = fast.next.next; if(slow === fast) { // 同一块内存 return true; } } return false; }

如果看不懂上面代码，可以先看看我掘金昨天关于快慢指针解决环形链表的文章：哨兵节点与快慢指针解决链表算法难题哨兵节点统一链表操作逻辑，简化边界处理；快慢指针高效解决环检测与倒数第N个节点等问题。 - 掘金

这个基础逻辑是解决 LCR 022 的前提，而 LCR 022 不仅要求判断是否有环，还需要找到入环的第一个节点，难度升级啦！

二、核心突破：如何找到入环第一个节点？ 📝

1. 问题衔接：先判环，再找入口

解决 LCR 022 的第一步，和基础题完全一致——用快慢指针判断链表是否有环。如果没有环，直接返回null；如果有环，就进入关键步骤：通过指针路程的数学关系，推导出入环节点的位置。

2. 关键推导：快慢指针的路程关联

这一步是核心！先明确变量定义：

设X：链表头head到入环第一个节点的距离（节点数）；
设C：环形部分的长度（环的节点总数）；
设Y：入环第一个节点到快慢指针相遇点的距离（节点数）。

接下来分析快慢指针的路程（从出发到相遇）：

由于fast一定比slow先入环，slow入环时fast可能已经绕环走了一圈、两圈、三圈…

最好情况slow一入环即与fast相遇。

最坏情况当slow入环时与fast的距离刚好是环的长度，此时两个指针每移动一步，之间的距离就缩小一步，不会出现内次刚好套圈的情况，因此在慢指针走完一圈之前，快指针肯定可以追上慢指针。

慢指针slow速度是 1 步/次，路程 =X + Y——先从 head 走到入环口（X 步），再沿环走 Y 步到达相遇点（未绕环）；
快指针fast速度是 2 步/次，且比slow先入环，相遇时已绕环n圈（n ≥ 1，追上至少绕 1 圈），路程 =X + nC + Y——先到入环口（X 步），绕环 n 圈（nC 步），再走 Y 步到相遇点。

示意图：

因fast路程是slow的 2 倍（速度 2 倍且同时出发），列等式：

2 × (X + Y) = X + nC + Y

化简后核心结论：

X = nC - Y

这个结论的意义是：链表头到入环口的距离 X，等于相遇点绕环 n 圈后再倒回 Y 步的距离。当n=1时（最易理解，fast 绕环 1 圈追上 slow），公式简化为X = C - Y，即“head 到入环口的距离 = 相遇点到入环口的环内剩余距离”。

因此，只要让一个指针从head出发，另一个指针从相遇点出发，两者以相同速度（1 步/次）前进，最终一定会在入环口相遇——因为前者走 X 步到入环口，后者走 X = nC - Y 步（绕 n 圈后再走 C-Y 步）也到入环口。

3. 代码实现与逐行解析

基于上面的推导，代码逻辑清晰，结合给出的代码逐行拆解：

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) { // 1. 初始化快慢指针，都从 head 出发 let fast = head; let slow = head; // 2. 快慢指针移动，判断是否有环 while(fast != null && fast.next != null) { fast = fast.next.next; // 快指针走 2 步 slow = slow.next; // 慢指针走 1 步 if(fast === slow) { // 相遇，说明有环，跳出循环 break; } } // 3. 无环情况：fast 走到末尾（null 或倒数第一个节点） if(fast === null || fast.next === null) { return null; } // 4. 找入环口：slow 回 head，两者同速前进 slow = head; while(slow != fast) { slow = slow.next; fast = fast.next; } // 5. 相遇点就是入环口 return slow; };

代码逻辑分 5 步，每一步都与推导对应：

第一步初始化指针，保证起点一致；
第二步通过快慢指针移动判环，fast先到末尾则无环；
第三步处理无环场景，直接返回null；
第四步是核心：slow回到head，fast留在相遇点，两者同速走；
第五步相遇时，指针指向的就是入环第一个节点，返回即可～

三、面试官可能会问的灵魂拷问 🤔

这道题的代码不算复杂，但面试官更看重你对原理的理解，这些问题一定要提前准备：

为什么快慢指针一定会相遇？会不会永远追不上？不会！因为fast速度比slow快 1 步/次，相当于两者之间的距离每次缩小 1 步。哪怕slow入环时，fast刚好在它身后（距离为C），最多C步后，fast一定会追上slow，且slow此时还没绕环 1 圈，修正：此前“内次刚好套圈”为笔误，不会出现每次都刚好错开的情况。
除了双指针，还有其他解法吗？两者对比如何？有！用哈希表（Set）存储遍历过的节点，每次遍历到新节点时，判断是否已在哈希表中：如果是，该节点就是入环口；如果不是，加入哈希表。对比：哈希表解法时间复杂度O(n)，但空间复杂度O(n)（需要存储节点）；双指针解法空间复杂度O(1)（仅用两个指针），是更优的解法，也是面试中更常考察的思路。
n公式推导中可以取任意正整数，为什么最终结果不受影响？因为nC是环的整数圈，fast从相遇点出发，走X = nC - Y步时，会先绕n圈回到相遇点附近，再走C - Y步到达入环口——这和绕 0 圈直接走C - Y步的终点完全一致。所以不管n是多少，两个指针最终都会在入环口相遇。