链表----环形链表II
🔥个人主页：Milestone-里程碑
❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>
<<Git>><<MySQL>>
🌟心向往之行必能至
一、题目回顾
给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
- 不允许修改链表本身。
- 进阶要求：使用O(1)空间复杂度解决问题（即不能用哈希表存节点）。
二、核心思路：快慢指针（Floyd 判圈算法）
1. 算法直觉
我们使用两个指针：
- 慢指针（slow）：每次走 1 步
- 快指针（fast）：每次走 2 步
如果链表有环，快指针最终一定会追上慢指针；如果无环，快指针会先走到链表末尾。
当两指针相遇后，我们将其中一个指针重置为头节点，然后两个指针同速前进，再次相遇的节点就是环的入口点。
三、数学推导：为什么相遇后同速能找到入口？
我们把链表拆成两部分：
- 非环部分：长度为
a（从 head 到环入口） - 环形部分：周长为
b
1. 第一次相遇时的路程
- 慢指针走过的路程：
a + x（x是在环内走的距离） - 快指针走过的路程：
a + x + n*b（n是绕环的圈数，n ≥ 1）
因为快指针速度是慢指针的 2 倍，所以：2(a+x)=a+x+n⋅b化简得：a+x=n⋅b⇒a=n⋅b−x
2. 寻找入口点
当两指针第一次相遇后：
让
slow留在相遇点，fast回到head然后两者都以每次 1 步的速度前进
fast走a步到达环入口slow从相遇点出发，走a步的路程为：x + a = x + (n·b - x) = n·b这意味着slow刚好绕环n圈，也到达了环入口
所以，两指针会在环入口点第二次相遇。
四、代码实现（C++）
cpp
运行
/** * 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) { ListNode* fast = head; ListNode* slow = head; // 第一步：快慢指针相遇，判断是否有环 while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (fast == slow) { // 相遇，存在环 // 第二步：将其中一个指针重置为 head，同速前进找入口 fast = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; // 相遇点即为环入口 } } // 无环，返回 nullptr return nullptr; } };代码关键点解析
- 循环条件：
while (fast && fast->next)是为了防止快指针访问空指针，避免越界。 - 相遇判断：当
fast == slow时，说明链表存在环。 - 寻找入口：将
fast重置为头节点，然后两指针同速前进，再次相遇时就是答案。
五、复杂度分析
- 时间复杂度：O(n)
- 第一次相遇：慢指针最多走
a + b步，快指针最多走2(a + b)步，均为线性时间。 - 第二次相遇：最多再走
a步，整体仍为 O (n)。
- 第一次相遇：慢指针最多走
- 空间复杂度：O(1)
- 仅使用了两个指针变量，没有额外的辅助空间。
六、对比：哈希表解法（辅助理解）
如果不限制空间复杂度，也可以用哈希表记录访问过的节点：
cpp
运行
class Solution { public: ListNode *detectCycle(ListNode *head) { unordered_set<ListNode*> visited; while (head) { if (visited.count(head)) { return head; } visited.insert(head); head = head->next; } return nullptr; } };- 优点：直观易懂，不需要复杂数学推导。
- 缺点：空间复杂度为 O (n)，不如快慢指针法高效。
七、总结
✅核心思想：利用快慢指针的速度差找到相遇点，再通过数学推导得出 “同速找入口” 的结论。✅记忆口诀：快两步，慢一步，相遇后，慢留头，同速走，入口出。✅适用场景：不仅适用于环形链表，还可以推广到其他需要寻找循环起点的问题。
这道题是链表经典题，理解快慢指针的数学原理，能帮你更好地掌握链表遍历和指针操作的技巧，也为后续更复杂的链表问题打下基础。