LeetCode 142. 环形链表 II
题目核心
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
注意：不允许修改链表。
这题是 141. 环形链表 的进阶版——141 只判断有没有环，142 要找出环的入口节点。
例 1：1 -> 2 -> 3 -> 4，尾连到 2（pos=1）
返回节点 2（入环点）
例 2：1 -> 2，尾连到 0（pos=0）
返回节点 1（入环点）
例 3：1 -> 2 -> null
返回 null解题思考过程
第一步：从 141 延伸
141 题用快慢指针判断了有没有环。现在要找环的入口，最直观的思路是：记录访问过的节点，第一个重复访问的就是入口。
第二步：哈希表法（直观）
遍历链表，把每个节点存进哈希表：
- 每访问一个节点，先查哈希表。
- 如果已存在 → 这个节点就是入口（第一次重复访问的节点）。
- 如果走到
null→ 无环。
这个方法简单直接，时间 O(n)，但空间 O(n)。
第三步：能不能 O(1) 空间
继续用快慢指针的思路。141 题中快慢指针相遇说明有环，但相遇点不一定是入口。
那相遇点和入口有什么关系？这就需要一点数学推导：
设：
a：头节点到入环点的距离。b：入环点到相遇点的距离。c：相遇点到入环点的距离（继续走回入口）。
环的长度 = b + c。
慢指针走的距离：a + b
快指针走的距离：a + b + n(b + c)（n 是快指针多绕的圈数，n ≥ 1）
快指针速度是慢指针的 2 倍，所以：
2(a + b) = a + b + n(b + c)
→ a + b = n(b + c)
→ a = n(b + c) - b
→ a = (n - 1)(b + c) + c意思是：从头节点走 a 步到达入口，等于从相遇点走 c 步再绕 (n-1) 圈到达入口。
所以：让一个指针从 head 出发，另一个从相遇点出发，两个都每次走 1 步，它们相遇的地方就是入口！
第四步：为什么 n=1 时也成立
第一次相遇时，快指针比慢指针多走了一圈，所以 n = 1：
a = (1-1)(b+c) + c = c也就是：从头节点走 a 步 = 从相遇点走 c 步，两者同时出发、同速前进，必然在入口相遇。
这个结论很优美，且实现起来很简单。
解法一：哈希表法
遍历链表，用 WeakMap 记录访问过的节点，第一个重复访问的就是入口。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
// 用 WeakMap 记录访问过的节点，key 为节点，第一次重复访问的就是入口
const map = new WeakMap();
while (head != null) {
if (map.has(head)) {
return head;
}
map.set(head, true);
head = head.next; // 别忘了向后移动
}
return null;
};易错点：原项目里的初版代码漏写了
head = head.next，会导致死循环（反复 set 同一个节点）；并且误把存的索引i当成返回值。本题要返回的是节点本身，不是索引。修正后如上。
代码逐行解释
const map = new WeakMap();用 WeakMap 而不是 Map：节点的 key 是对象引用，WeakMap 不会阻止节点被回收，更安全。
while (head != null) {
if (map.has(head)) {
return head;
}
map.set(head, true);
head = head.next;
}- 每到一个节点，先查是否访问过。
- 访问过 → 直接返回该节点（它就是入口）。
- 没访问过 → 记录下来，继续往后走。
- 走到
null→ 无环，返回null。
为什么第一个重复访问的就是入口？
因为遍历是顺着 next 走的，入环点是从环外进入环内的第一个节点。当绕了一圈回到入口时，它会被第二次访问到，此时就是入口。环内其他节点不会比入口更早被重复访问。
执行过程示例
链表：1 -> 2 -> 3 -> 4 -> 2（4 指回 2）
head=1: map 无 1，set{1}, head=2
head=2: map 无 2，set{1,2}, head=3
head=3: map 无 3，set{1,2,3}, head=4
head=4: map 无 4，set{1,2,3,4}, head=2
head=2: map 有 2！返回节点 2（入口）解法二：快慢指针法（O(1) 空间）
利用前面推导的结论：快慢指针相遇后，让一个指针从 head 出发，和慢指针同速前进，相遇点就是入口。
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
// 快慢指针找相遇点，再让一个指针从头出发，和慢指针同速前进，相遇即入口
let slow = head;
let fast = head;
// 第一阶段：判断是否有环，找到相遇点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
// 有环，进入第二阶段
let ptr = head;
while (ptr !== slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr; // 相遇点就是入口
}
}
return null; // 无环
};原项目里的快慢指针版只写了注释没实现，这里补全。
代码逐行解释
第一阶段：找相遇点
let slow = head;
let fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {和 141 题完全一样：慢指针走 1 步，快指针走 2 步。相遇说明有环。
第二阶段：找入口
let ptr = head;
while (ptr !== slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;ptr从head出发。slow停在相遇点。- 两个都每次走 1 步。
- 根据前面的推导
a = c，它们走的步数相同时会同时到达入口，所以ptr === slow时就是入口。
无环情况
return null;如果第一阶段循环正常结束（快指针到末尾），说明无环，返回 null。
执行过程示例
链表：1 -> 2 -> 3 -> 4 -> 2（4 指回 2，入口是节点 2）
设 a=1（head 到入口），环 2->3->4->2。
第一阶段（找相遇点）：
初始 slow=1, fast=1
第 1 轮：slow=2, fast=3
第 2 轮：slow=3, fast=2
第 3 轮：slow=4, fast=4 → 相遇！
第二阶段（找入口）：
ptr=head=1, slow=4（相遇点）
第 1 步：ptr=2, slow=2 → ptr === slow，相遇！
返回节点 2（入口）ptr 走了 1 步到达入口 2，slow 从相遇点 4 走 1 步也到达入口 2，正好印证 a = c。
两种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 哈希表法 | O(n) | O(n) | 直观易懂，实现简单 |
| 快慢指针 | O(n) | O(1) | 空间最优，需要数学推导 |
- 追求简洁：哈希表法，几行代码搞定，不容易写错。
- 追求最优 / 面试：快慢指针，O(1) 空间，体现对链表和数学的理解。
复杂度分析
- 时间复杂度：两种都是
O(n)。哈希法遍历一次；快慢指针法两个阶段加起来最多走 2n 步。 - 空间复杂度：哈希法
O(n)；快慢指针O(1)。
关键结论记忆
快慢指针找环入口的核心结论：
从头节点到入环点的距离
a，等于从相遇点到入环点的距离c（第一次相遇时）。
所以让两个指针一个从头、一个从相遇点，同速前进，相遇处就是入口。这个结论不需要记公式，记住"a 等于 c"即可。