力扣142.环形链表 II
这道题是面试高频考点，也是 LeetCode Hot100 中的经典题目，我们先讲简单的哈希表解法，再重点分析空间复杂度 O (1) 的快慢指针最优解。
一、简单解法：哈希表（Set 容器）
核心思路是利用哈希表的 “唯一性” 记录遍历过的节点：
- 遍历链表时，将每个节点的地址插入 C++ STL 的
set<ListNode*>容器； - 若当前节点已存在于
set中，说明该节点就是环的第一个节点； - 若遍历到链表末尾仍无重复节点，则链表无环。
该方法逻辑简单易懂，此处不再展开赘述，接下来重点讲解更优的快慢指针解法。
二、最优解法：快慢指针（空间复杂度 O (1)）
1. 第一步：判断链表是否有环
利用 “一快一慢” 两个指针遍历链表，通过是否相遇判断是否存在环：
- 快指针（fast）：每次走 2 步；
- 慢指针（low）：每次走 1 步；
- 若链表无环：fast 指针会先走到链表末尾（
fast == nullptr或fast->next == nullptr），两个指针永远不会相遇； - 若链表有环：fast 指针会在环内 “追上” low 指针，最终两者必定相遇（因为 fast 每次比 low 多走 1 步，相当于每次向 low 靠近 1 步）。
（无环)
(有环)
2. 第二步：找到环的第一个节点
当确认链表有环后，我们需要进一步定位环的入口，先定义几个关键长度：
a：链表头结点到环入口的距离；b：环入口到快慢指针相遇点的距离；c：相遇点回到环入口的距离。
推导：
- 慢指针（low）走到相遇点时，总路程为：
a + b； - 快指针（fast）走到相遇点时，总路程为：
a + b + n×(b + c)（n为 fast 绕环的圈数）； - 由于 fast 速度是 low 的 2 倍，因此路程也为 2 倍：
2×(a + b) = a + b + n×(b + c)； - 化简公式得：
a + b = n×(b + c)。
为什么 n=1？（fast 必在 low 入环第一圈追上）
很多同学会疑惑 fast 是否会绕多圈才追上 low，答案是不会：
- 当 low 刚进入环时，fast 已经在环内，且两者的距离小于等于环的总长度 L；
- fast 每次比 low 多走 1 步，相当于 以 1 步 / 次的速度追上 low；
- 最多需要 L 步就能追上，而 low 走 L 步刚好是环的一圈，因此 low 入环后第一圈内必被 fast 追上。
因此n=1，代入公式继续化简：a + b = b + c → a = c（头结点到环入口的距离 = 相遇点到环入口的距离）。
3. 第三步：定位环的第一个节点
基于a = c的核心结论，定位环入口：
- 当快慢指针相遇后，将 fast 指针重新移回链表头结点；
- 让 fast 和 low 指针以相同速度（每次走 1 步） 同时前进；
- 当两者再次相遇时，所处的位置就是环的第一个节点。
算法复杂度
- 时间复杂度：O (n)
- 空间复杂度：O (1)
这道题算法题主要考察了两个知识点
- 快慢指针相遇 → 链表有环；
- 相遇后 fast 回头结点，两指针同速前进 → 相遇点即为环入口。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(head==NULL||head->next==NULL) return NULL; ListNode*fast =head; ListNode*low =head; while(fast!=NULL&&fast->next!=NULL) { fast=fast->next->next; low=low->next; if(fast==low) break;//fast和low相遇 } if(fast!=low) return NULL; fast=head; while(fast!=low) { fast=fast->next; low=low->next; } return fast; } };
