已解答
中等
相关标签
相关企业
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围
[0, 104]内-105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
为什么两个指针从相遇点和起始点出发，最终会在环的开头相遇？
关键推导回顾
设：
X= 链表头节点到环入口的距离Y= 环入口到快慢指针相遇点的距离Z= 相遇点沿指针方向回到环入口的距离环的长度
L = Y + Z
当快慢指针相遇时：
慢指针步数：
S = X + Y快指针步数：
2S = X + Y + n × L（n是快指针绕环的圈数，n ≥ 1）
联立方程：
math
2(X + Y) = X + Y + nLmath
X + Y = nLmath
X = nL - Y将 L = Y + Z 代入：
math
X = n(Y + Z) - Y = (n-1)L + Z物理意义
X（头到入口） =Z（相遇点到入口） +(n-1)L（整数倍环长）这意味着：
从链表头走到环入口的距离X，等于从相遇点走到环入口的距离Z加上(n-1)圈环的长度。
双指针移动过程分析
指针设置：
指针A：从链表头出发
指针B：从相遇点出发
移动规则：
两指针每次都只走 1 步，速度相同。相遇时刻：
当指针A走了
X步到达环入口时：指针B走了
X步将
X = (n-1)L + Z代入：指针B的总移动距离 =
(n-1)L + Z这相当于：先走
Z步到达环入口，再绕环走(n-1)圈（每圈L步）
最终位置：
指针A：停在环入口
指针B：走完
Z步到达环入口后，又绕了(n-1)圈，最终也停在环入口
→ 两指针在环入口相遇！
示例演示（n=1 最简单情况）
链表结构：1 → 2 → 3 → 4 → 5 → 3（环入口是节点3，相遇点设为节点5）
计算：
X= 头到入口 = 2步（1→2→3）Y= 入口到相遇点 = 2步（3→4→5）Z= 相遇点到入口 = 2步（5→6→3，环长 L=4）n = 1（快指针绕1圈）
双指针移动：
结果：在第2步时，两指针在环入口3处相遇。
示例演示（n=2 复杂情况）
链表结构：1 → 2 → 3 → 4 → 5 → 6 → 3（环入口3，环长 L=4，相遇点设为节点6）
计算：
X= 头到入口 = 2步（1→2→3）Y= 入口到相遇点 = 3步（3→4→5→6）Z= 相遇点到入口 = 1步（6→3）n = 2（快指针绕2圈）X = (2-1)×4 + 1 = 5
双指针移动：
结果：在第5步时，两指针在环入口3处相遇。
指针B：先走
Z=1步到入口，再绕1圈（4步）后回到入口指针A：走
X=5步到达入口
核心结论
必然在环入口相遇：
无论n是多少，当指针A走完X步到达入口时，指针B一定恰好走完Z + (n-1)L步，相当于从相遇点走到入口后再绕(n-1)圈，最终也停在入口。数学保证：
公式X = (n-1)L + Z决定了两个指针的路径终点必然重合于环入口。时间复杂度：
最多遍历链表长度 2 遍（找相遇点 + 双指针移动），仍是 O(n)。
这就是 Floyd 环检测算法的精妙之处！ 🚀
最坏情况：
当慢指针刚进入环时，快指针正好在慢指针的前一个位置（即距离慢指针 L−1L−1 步）。
此时，快指针需要追赶 L−1L−1 步才能与慢指针相遇。
慢指针的移动：
在这 L−1L−1 步中，慢指针自己也会走 L−1L−1 步。
但由于环的长度是 LL，所以慢指针最多走 L−1L−1 步，不会走完一整圈（即不会回到环的起始点）。
数学关系：
快指针走的步数 = 2×(L−1)2×(L−1)。
慢指针走的步数 = L−1L−1。
由于快指针速度是慢指针的 2 倍，两者最终会在慢指针走 L−1L−1 步时相遇。
举例验证（环长 L=4L=4）
初始状态：
慢指针刚进入环（位置 0）。
快指针在位置 3（距离慢指针 L−1=3L−1=3 步）。
移动过程：
结果：
慢指针走了 3 步（L−1=3L−1=3），未走完一圈（4 步）。
快指针走了 6 步（2×32×3），绕环 1 圈半。
为什么这是最坏情况？
如果快指针离慢指针更近（比如距离 2 步），相遇会更快（只需 2 步）。
只有距离 L−1L−1 时，需要最多的 L−1L−1 步才能相遇，因此这是最坏情况。
对算法的影响
由于慢指针最多走 L−1L−1 步，因此：
公式 S=X+YS=X+Y 中，Y<LY<L（慢指针在环内走的步数 YY 不会超过 L−1L−1）。
这保证了快慢指针方法的时间复杂度是 O(n)O(n)，且能正确找到环入口。
总结
你的理解完全正确：在最坏情况下（快指针距离慢指针 L−1L−1 步），慢指针需要走 L−1L−1 步才会被快指针追上，且不会走完一整圈。
这解释了为什么 S=X+YS=X+Y 无需考虑慢指针多走圈数，因为 Y<LY<L。
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
//对是否存在环进行判断
ListNode* fast = head;
ListNode* slow = head;
//获取关键节点
ListNode* strat = head;
ListNode* meetNode = nullptr;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
meetNode = fast;
break;
}
}
if (meetNode == nullptr) {
return nullptr;
}
//如果存在环 则从起点和meetNode同时开始走
while (strat != meetNode) {
strat = strat->next;
meetNode = meetNode->next;
}
//此时相遇的节点就是环的起点
return strat;
}
};