本文概览：本文以LeetCode经典题目"环形链表 II"为例，从暴力哈希表解法入手，逐步优化到快慢指针 O(1) 空间解法，重点讲解快慢指针第一次相遇后的数学推导过程，证明为什么第二次相遇的位置就是环的入口

一、题目

环形链表II题目

二、题目分析

给定一个链表的头节点 head，判断链表中是否有环，如果有环，返回环的入口节点；如果没有环，返回 null

目标：找到环的入口节点，空间复杂度要求 O(1)

核心难点：不仅要判断是否有环，还要精确定位环的入口

思路概览

Java实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode detectCycle(ListNode head) {
    // 快慢指针判断是否有环
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        // 第一次相遇
        if (slow == fast) {
            // 让fast回到起点，slow留在相遇点
            fast = head;
            // 两个指针都一步一步走，第二次相遇就是环的入口
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

思路简要说明

  1. 快慢指针判断有环：快指针每次走两步，慢指针每次走一步，如果相遇说明有环

  2. 第一次相遇：记录相遇位置，此时慢指针走了 s 步，快指针走了 2s 步

  3. 第二次相遇：让快指针回到起点，两个指针都一步一步走，再次相遇的位置就是环的入口

三、思路详解

暴力解法入手

最直观的想法是：遍历链表，把每个节点都存到哈希表中。如果遇到一个节点已经在哈希表中存在了，说明这个节点就是环的入口（因为环的入口是第一个重复的节点）

1
2
3
4
5
6
7
8
9
10
11
public ListNode detectCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) {
            return head;  // 第一个重复的节点就是环的入口
        }
        visited.add(head);
        head = head.next;
    }
    return null;
}
  • 时间复杂度：O(n)，遍历一次链表
  • 空间复杂度：O(n)，哈希表存储所有节点
  • 核心瓶颈：需要额外 O(n) 空间存储节点
  • 关键思考：能否不用哈希表，只用指针来找到环的入口？

快慢指针解法

第一步：判断是否有环（快慢指针）

这个和"环形链表 I"一样：快指针每次走两步，慢指针每次走一步。如果链表有环，快指针一定会追上慢指针；如果没环，快指针会先到达 null

第二步：找到环的入口（核心难点）

快慢指针第一次相遇后，怎么找到环的入口？这里需要数学推导

先理解快慢指针的运动过程

假设链表结构如下：

1
2
3
4
5
6
7
8
链表头 → a 步 → 环入口 → b 步绕一圈 → 回到环入口

    a              b
[1]→[2]→[3]→[4]→[5]→[6]
              ↑_________|

a = 3（从1到4的距离）
b = 3（环的长度：4→5→6→4）

快指针速度是慢指针的 2 倍。当慢指针刚进入环时（走了 a 步到达环入口），快指针已经走了 2a 步，此时快指针在环内的某个位置

由于快指针比慢指针快，它会在环内"追上"慢指针。追上的时候，快指针一定已经在环内转了若干圈了

数学推导

设：

  • a：链表头到环入口的距离（非环部分的长度）
  • b：环的长度
  • s：慢指针第一次相遇时走过的总路程

当快慢指针第一次相遇时：

  • 慢指针走了 s 步
  • 快指针走了 2s 步（因为快指针速度是慢指针的 2 倍）

快指针比慢指针多走了 s 步。这多走的 s 步是什么？

想象两个人在操场上跑步，一个人速度是另一个的 2 倍。速度快的人追上速度慢的人时，速度快的人一定比速度慢的人多跑了整数圈

同理，快指针追上慢指针时，快指针比慢指针多走的路程一定是环长度的整数倍。也就是说，快指针在环内多转了 n 圈（n ≥ 1）

所以快指针的路程可以表示为：s + n×b（s 是慢指针的路程，n×b 是快指针在环内多转的圈数）

而快指针的实际路程是 2s，所以：

1
2
2s = s + n×b
s = n×b

也就是说，慢指针第一次相遇时走过的路程 s 是环长度 b 的整数倍

关键结论

一个指针从链表头出发，走了 a + n×b 步后，它的位置一定在环的入口

为什么？因为从链表头走 a 步到达环入口，再走 n 圈（n×b 步）还是回到环入口。在环里转多少圈，位置不变，都在环入口

现在我们知道慢指针走了 s = n×b 步。如果让慢指针再走 a 步，它的总路程就是 n×b + a = a + n×b，正好到达环入口！

问题：怎么让慢指针恰好走 a 步？

我们不知道 a 是多少。但注意到一个关键事实：

  • 快指针从链表头出发，走 a 步，到达环入口
  • 慢指针从相遇点出发，走 a 步，总路程 = n×b + a = a + n×b，也到达环入口

两个人，一个从头走 a 步，一个从相遇点走 a 步，同时到达环入口！

这就给了我们一个巧妙的办法：

  • 让快指针回到链表头（此时快指针在"起点"，走了 0 步）
  • 让慢指针留在相遇点（此时慢指针走了 n×b 步）
  • 两个指针都一步一步往前走

当快指针走了 a 步时，它到达环入口（因为从头走 a 步就是环入口）

当慢指针也走了 a 步时，它的总路程是 n×b + a = a + n×b，也到达环入口！

所以，两个指针都一步一步走，再次相遇的位置就是环的入口

用图来理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
第一次相遇时：

链表头 ──a──→ 环入口 ──x──→ 相遇点
                ↑_____b-x_____|

slow走了：a + x 步（从头走到相遇点）
fast走了：a + x + n×b 步（从头走到相遇点，再在环内转了n圈）

因为 fast = 2×slow，所以：
a + x + n×b = 2×(a + x)
n×b = a + x

第二次相遇：
让fast回到链表头，slow留在相遇点，都一步一步走

fast从头走a步：到达环入口
slow从相遇点走a步：
  相遇点到环入口的距离 = b - x
  但 n×b = a + x，所以 a = n×b - x
  slow走的总路程 = (a + x) + a = a + x + n×b - x = a + n×b
  到达环入口！

图示说明

以 3 → 2 → 0 → -4 → 2（环入口是节点 2）为例：

1
2
3
4
5
6
链表结构：
3 → 2 → 0 → -4
    ↑_________|

a = 1（从3到环入口2的距离）
b = 3（环的长度：2→0→-4→2）

第一次相遇：

步骤 slow fast
初始 3 3
1 2 0
2 0 2
3 -4 -4

slow 走了 3 步（3→2→0→-4），s = 3
fast 走了 6 步（3→0→2→-4→2→0→-4），2s = 6

验证：s = 3 = 1×b，确实 s 是 b 的整数倍（n=1）

第二次相遇：

  • fast 回到起点 3
  • slow 留在相遇点 -4
  • 两个指针都一步一步走
步骤 slow fast
0 -4 3
1 2 2

slow 从 -4 走 1 步到 2，总路程 = 3 + 1 = 4 = a + n×b = 1 + 1×3 ✓
fast 从 3 走 1 步到 2，总路程 = 1 = a ✓

  • 时间复杂度：O(n)，第一次相遇最多遍历 n 步，第二次相遇最多遍历 a 步（a < n）
  • 空间复杂度：O(1)，只用了两个指针