环形链表与相交链表

这一篇解决链表里最"数学"的两个模型：判环与找交点。它们不涉及增删节点，核心武器都是双指针——但用法和前面的反转、删除完全不同：一个靠速度差，一个靠长度差。

一、判环：快慢指针（LeetCode 141）

题目：判断链表中是否有环。

1.1 思路

如果链表有环，用普通方式遍历会永远转圈出不来。反过来想：让两个指针在环里赛跑，跑得快的一定会从后面追上跑得慢的——就像操场上跑圈，快的选手迟早套慢选手一圈。

于是有了快慢指针（Floyd 判圈法）：

慢指针每次走 1 步，快指针每次走 2 步；
若无环，快指针先到达 null，结束；
若有环，两者都会进入环内，快指针每轮比慢指针多走 1 步，差距每轮缩小 1，最终必然追上（相遇在环内某节点）。

1.2 为什么快 2 慢 1 必相遇

关键在于"每轮差距缩小 1"这个事实。进入环后，以慢指针为参照系（想象慢指针静止），快指针每轮相对前移 1 步。环的长度是有限的，相对距离从某个值开始每轮减 1，减到 0 的时刻就是相遇时刻——中间不会跳过。

一个常见疑问：快指针一次跳 2 步，会不会正好跨过慢指针导致永远错开？不会。所谓"跨过"是绝对位置的描述；在追逐问题上，两者距离每轮严格减 1，从距离 1 变成距离 0 的那轮就是重合，不存在跳到 -1 再绕一圈的情况。若是快 3 慢 1，每轮减 2，反而可能从距离 2 直接跳到 0 的对侧错过，判圈效率反而不可控。

1.3 代码

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        // 只需保证 fast 和 fast.next 不为空，fast.next.next 才安全
        while (fast != null && fast.next != null) {
            slow = slow.next;      // 走 1 步
            fast = fast.next.next; // 走 2 步
            if (slow == fast) return true; // 环内相遇
        }
        return false; // fast 撞到 null，说明没有环
    }
}

注意循环条件是 fast != null && fast.next != null——判断的是快指针能不能安全地走两步，慢指针永远走不到空处，不用检查。

二、找入环点：数学推导（LeetCode 142）

题目：若有环，返回环的入口节点；无环返回 null。141 只回答"有没有"，142 要回答"在哪"。

2.1 建立模型

        a
head --------+
             |          环
             v      b -> b -> b
             +----> (入口)     |
              ^                |
              +----- b --------+  (环长 b，设相遇点距入口 c)

设三个量：

a：头结点到入环点的距离；
b：环的长度；
c：入环点到相遇点的距离（沿前进方向量）。

2.2 推导 a = c + (n-1) 圈

相遇时：

慢指针走了 a + c 步（它没绕圈，进环后走到相遇点就停了）；
快指针走了 a + c + n·b 步，比慢指针多绕了 n 圈（n ≥ 1）；
快指针速度是慢指针 2 倍，路程也是 2 倍。

列方程：

2(a + c) = a + c + n·b
=>  a + c = n·b
=>  a     = n·b - c
=>  a     = c + (n - 1)·b

这个等式读出来就是结论：从相遇点走 a 步（等价于走 c 步再多绕 n-1 整圈），恰好回到入环点。

于是算法诞生：

快慢指针走到相遇；
让一个指针回到 head，另一个留在相遇点；
两个指针都改为每次走 1 步，再次相遇的地方就是入环点——因为两者到入环点的距离相同（都是 a，或 c 加上若干整圈）。

2.3 代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {           // 第一阶段：相遇
                ListNode p = head;        // p 回起点
                while (p != slow) {       // 第二阶段：同速前进
                    p = p.next;
                    slow = slow.next;
                }
                return p;                 // 再相遇处即入环点
            }
        }
        return null;
    }
}

担心"第二阶段会不会错过"的读者可以代入具体数字验证：比如 a=3、b=5，由 a = c + (n-1)·b，取 n=1 得 c=3。相遇后 p 从头走 3 步到入环点，slow 从相遇点走 3 步（恰好 = c）也到入环点，两人同时到达。

三、相交链表（LeetCode 160）

题目：两个单链表可能在某节点开始共享同一段尾巴，找到相交的起始节点；不相交返回 null。注意比较的是节点引用相同，不是值相同。

链表A:  a1 -> a2 ──┐
                   ├──> c1 -> c2 -> c3
链表B:  b1 -> b2 -> b3 ──┘（汇入 c1）

3.1 思路：先对齐长度再同步走

相交之后两链表走的是同一条路，交点之后长度必然一致。因此长度差全部来自交点之前。做法：

分别数出两链表长度 lenA、lenB；
让长的那条先走 |lenA - lenB| 步，把尾巴对齐；
两指针同步前进，第一次引用相等处就是交点（含都不相交时同时走到 null 的情况）。

3.2 代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { lenA++; curA = curA.next; }
        while (curB != null) { lenB++; curB = curB.next; }
 
        curA = headA;
        curB = headB;
        // 让 curA 始终代表较长的链表
        if (lenB > lenA) {
            ListNode t = curA; curA = curB; curB = t;
            int tl = lenA; lenA = lenB; lenB = tl;
        }
        // 长的先走差值步
        for (int i = 0; i < lenA - lenB; i++) {
            curA = curA.next;
        }
        // 同步走，直到相遇（或同时为 null）
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
}

3.3 为什么不能从后往前找

单链表无法回头，"找两条路最后一个相同节点再往回退"在单向结构上行不通——这正是 160 必须绕到"从前往后对齐"的原因。顺带一提，这道题在 LeetCode 上对应面试题 02.07，思路一致。

四、易错点小结

141 的循环条件写错：写成 fast != null 漏了 fast.next 判空，fast.next.next 直接 NPE。
142 第二阶段忘了同速：相遇后如果还保持 2 倍速找入环点，就永远绕圈了。
160 比较写成 curA.val == curB.val：值相等不代表是同一个节点，题目要的是引用相等。
160 忘了"同时走到 null"也是出口：不相交时两指针同时变 null，循环 curA != curB 自然终止，返回 null，逻辑已覆盖，无需额外分支。
推导记不住没关系，但要在纸上独立推一遍 a = c + (n-1)b，面试现场现推比硬背可靠。

参考

代码随想录 · 链表专题