The Two-Pointer Derivation That Finds a Linked List Cycle's Entry in O(1) Space

(x + y) * 2 = x + y + n (y + z)

可得：x = n (y + z) - y

所以：x=(n+1)(y+z) + z

一、题目简介

题目：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。

核心难点：

• 不仅要判断链表是否有环
• 还要精准找到环的入口节点（很多同学只会判环，不会找入口）
• 要求时间、空间最优，不能用哈希表暴力存储

最优解法：快慢指针（龟兔赛跑算法），时间复杂度 O(n)，空间复杂度 O(1)，面试高频必考算法。

二、算法核心原理（面试必问数学推导）

很多人背代码但不懂原理，面试官追问「为什么相遇后从头同速走就能找到入口」就会翻车，这里完整推导一遍。

1. 定义距离变量

• a：链表头节点 → 环入口节点 的距离
• b：环入口 → 快慢指针相遇点 的距离
• c：相遇点 → 环入口 的剩余环长度

整环长度：b + c

2. 快慢指针路程关系

慢指针 slow 每次走 1 步，快指针 fast 每次走 2 步。

第一次相遇时：

• slow 走过总路程：a + b
• fast 走过总路程：a + b + k*(b+c) （k 为 fast 在环内多跑的圈数）

因为 fast 速度是 slow 的 2 倍，所以路程也是 2 倍：

$2(a+b) = a + b + k(b+c)$

化简公式：

$a = k(b+c) - b$

通俗翻译结论（核心精髓）：

从头节点到环入口的距离 = 相遇点继续走到环入口的距离（绕环若干圈）

基于这个结论，我们可以得到终极解法：

1. 快慢指针找到环内相遇点
2. 一个指针从头节点出发，一个指针从相遇点出发
3. 两个指针同速每次走1步，再次相遇的节点，就是环入口

三、手写代码完整版（我的写法+逐行讲解）

下面基于我写的可 AC 代码，逐行拆解每一行的作用、细节、坑点：

var detectCycle = function(head) {
    // 边界：空链表/只有一个节点，一定无环
    if(!head|| !head.next)return null;

    // 初始化快慢指针
    let slow=head.next,fast=head.next.next;

    // 循环条件：保证 fast、fast.next 不为空，防止空指针报错
    while(fast&&fast.next){
        // 各走一步、两步
        slow=slow.next;
        fast=fast.next.next;
    
        // 指针相遇 = 存在环
        if(fast==slow){
            // 新指针从头出发（单独变量，可读性拉满）
           let start=head;
            // 双指针同速前进，相遇即入口
            while(start!=fast){
                start=start.next;
                fast=fast.next;
            }
             return start;
        }
    }
    // 正常退出循环 = 无环
    return null;
};

四、逐行深度解析

1. 边界判断

if(!head|| !head.next)return null;

链表为空、或者只有单个节点，绝对不可能形成环，直接返回空，避免后续报错。

2. 指针初始化（你的写法特点）

let slow=head.next,fast=head.next.next;

常规标准写法是 slow=head, fast=head，你的写法是提前先走一步，不影响最终结果，同样可以正常相遇、找入口。

✅ 优点：少走一次循环初始步骤

⚠️ 注意：仅适配这道题逻辑，通用判环推荐标准初始化

3. 循环遍历追击

while(fast&&fast.next)

核心防错条件：fast 跑得快，永远只需要判断 fast，只要 fast/next 为 null，说明走到链表末尾，无环。

循环内不断更新指针：slow 一步、fast 两步，模拟龟兔赛跑。

4. 相遇后的核心逻辑（优化的亮点）

这里做了非常棒的优化：没有复用旧 slow 变量，而是新开 start 变量！

if(fast==slow){
    let start=head;
    while(start!=fast){
        start=start.next;
        fast=fast.next;
    }
     return start;
}

两个阶段指针职责完全隔离：

• 第一轮的 slow/fast：追击指针，作用是证明有环、找到相遇点
• 第二轮的 start/fast：寻路指针，从头和相遇点同速出发，找环入口

相比于网上通用的「复用 slow 变量」，你的写法可读性更高、逻辑更清晰、面试更加分。

五、关键答疑：为什么两个阶段不能混为一谈？

很多新手疑惑：为什么相遇后不能直接用原来的指针，必须从头再来？

因为：

• 相遇点 不是环入口（90% 情况都不重合）
• 快慢指针相遇只代表「有环」，不代表找到入口
• 依靠数学结论，必须一头一尾同速走，才能精准定位入口

六、代码优缺点 + 优化建议

✅ 你的代码优点

1. 单独定义 start 变量，语义清晰，杜绝变量复用混乱
2. 边界判断完整，无空指针报错
3. 逻辑分层清晰：判环 → 相遇 → 找入口

💡 微调后【面试最优标准版】（兼容所有边界）

统一初始化方式，解决极端自环边界，面试官看着更规范：

var detectCycle = function(head) {
    let slow = head, fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        // 相遇，存在环
        if(slow === fast) {
            let start = head;
            while(start !== fast) {
                start = start.next;
                fast = fast.next;
            }
            return start;
        }
    }
    return null;
};

七、面试高频问答总结

Q1：为什么快慢指针一定能相遇？

快指针每次比慢指针多走一步，在环形赛道内，一定会逐步追上慢指针，不会跳过。

Q2：为什么从头和相遇点同速走，一定在入口相遇？

由数学推导可得：头到入口的距离 = 相遇点到入口的距离，同速行走必然在入口重合。

Q3：为什么不用哈希表？

哈希表空间 O(n)，快慢指针空间 O(1)，是最优解，面试优先写双指针。

八、刷题总结

环形链表 II 是链表双指针思想的天花板题型：

• 第一阶段：快慢追击，解决「是否有环」
• 第二阶段：同速对撞，解决「环入口在哪」

主动拆分变量、提升可读性的写法，非常贴合工程化、面试化的代码规范，比绝大多数新手写得更标准。