【力扣每日一题】2023.7.30 环形链表2

题目：

示例：

分析：

这道题属于是那种知道解法就很简单，不知道解法就很难独立想出来的那种，我们只需要稍微记住这类题的固定解法就可以。

所以接下来我先说解法，再解释为什么解法可以解出来。

那么我们都知道使用快慢指针可以找出一个链表是否有环（不知道的去看看我昨天的每日一题题解），我们需要找出这个环的路口，我们在快慢指针相遇的时候就可以判断出链表有环，并且开始寻找。

我们将快指针移动回链表的开头，并且将快指针的速度调整为每次移动一格，然后再让快慢指针再次移动，直到它们相遇，相遇的位置就是环的入口。

这看起来有些不可思议是吗，怎么会这么简单，而且怎么就可以知道它们再次相遇的点就是环入口了，小朋友你是否有很多问号？？？

那么这涉及到了数学，因此这类题我的建议就是记住对应的模板，不要深究怎么样才可以在下次遇到类似的题目时自己可以从零开始推导出来，这不是普通人能干的。

首先我们把链表开头到环入口的这段距离称为A，把环入口到快慢指针第一次相遇的地方的这段距离称为B，把快慢指针第一次相遇的地方直走走回环的入口的这段距离称为C，接下来可以开始推导了。

我们知道，快指针走过的的路程等于A+B+C+B，而慢指针走过的路程等于A+B。

我们又知道，每次快指针移动两格，慢指针移动一格，因此快指针走过的路程是慢指针的两倍。

我们就可以得到这样的式子：

A+B+C+B = 2*（A+B） = A+A+B+B

 化简一下就变成了：

C=A

 神奇吗同志们，从链表到环入口的距离（A）就等于在快慢指针第一次相遇的地方再次走到环入口，因此我们之前的操作就可以得到解释了，让慢指针接着走，然后让快指针调整速度以后从头开始走，走到它们第二次相遇，那就是环的入口了。

代码：

class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head==nullptr) return nullptr;//快慢指针ListNode* fast=head;ListNode* slow=head;while(fast!=nullptr && fast->next!=nullptr){//快指针每次移动两次,慢指针每次移动一次slow=slow->next;fast=fast->next->next;//如果相遇则是有环,开始寻找入口if(fast==slow){fast=head;while(fast!=slow){fast=fast->next;slow=slow->next;}return fast;}}return nullptr;}
};