【算法--链表】142.环形链表中Ⅱ--通俗讲解如何找链表中环的起点

一、题目是啥？一句话说清

给定一个链表，如果链表有环，返回环的起始节点；如果无环，返回 null。不能修改链表。

二、解题核心

使用快慢指针法：先找到快慢指针的相遇点，然后让一个指针从头开始，另一个从相遇点开始，以相同速度移动，它们再次相遇的点就是环的入口。

这就像两个人在环形跑道上跑步：

1. 快的人速度是慢的人的两倍，他们最终会相遇。
2. 相遇后，让快的人回到起点，然后两人以相同速度跑步，他们再次相遇的地方就是跑道的入口。

三、关键在哪里？（3个核心点）

想理解并解决这道题，必须抓住以下三个关键点：

1. 快慢指针的相遇点

• 是什么：快指针每次走两步，慢指针每次走一步，如果存在环，它们一定会相遇。
• 为什么重要：相遇点是我们找到环入口的起点。

2. 数学关系推导

• 是什么：从头节点到环入口的距离 = 从相遇点到环入口的距离 + n圈环长。
• 为什么重要：这个数学关系保证了从头节点和相遇点同时出发的两个指针，会在环入口相遇。

3. 第二次移动的同步速度

• 是什么：找到相遇点后，两个指针都以每次一步的速度移动。
• 为什么重要：这样能确保它们正好在环入口相遇，而不是错过。

四、看图理解流程（通俗理解版本）

假设链表：1 → 2 → 3 → 4 → 5 → 3（形成环，5指向3）

1. 第一階段：找到相遇点

   • 慢指针每次走一步，快指针每次走两步。
   • 慢指针路径：1 → 2 → 3 → 4 → 5 → 3 …
   • 快指针路径：1 → 3 → 5 → 4 → 3 → 5 …
   • 它们在节点4相遇（示例中可能相遇在其他点，但总会相遇）。

2. 第二階段：找到环入口

   • 将快指针重新指向头节点（节点1）。
   • 快指针和慢指针都每次走一步：
     • 快指针从1开始：1 → 2 → 3
     • 慢指针从4开始：4 → 5 → 3
   • 它们在节点3相遇，节点3就是环的入口。

五、C++ 代码实现（附详细注释）

#include <iostream>
using namespace std;// 链表节点定义
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};class Solution {
public