题目要求
Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
Follow up:
Can you solve it without using extra space?
如何找到环的第一个节点？
根据题目意图，我们可以构建如下模型：
设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是v,2v。
由slow和fast第一次在点Z相遇，我们可以得出以下等式：
2(a+b)=(a+2b+c)
=> a=c
由此可见，a和c的长度一样。因此我们可以将slow重新定位到头结点，然后fast与slow以相同的速度前进，相遇的节点Y则是环的开始节点。
代码实现：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow=head;
ListNode* fast=head;
while(true){
if(fast==nullptr||fast->next==nullptr){
return nullptr;
}
slow=slow->next;
fast=fast->next->next;
if(fast==slow){
break;
}
}
slow=head;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
};