题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

题目分析

1. 根据题意可知，本题需要解决两个问题：一是判断当前链表中是否存在环，使用快慢指针可以解决这个问题；二是找到环的入口点；
2. 在链表中存在环的情况下，如何找到环的入口点？
   首先假设链表头部到环的入口节点前有x个节点(不包括环的入口点)，链表的环中有y个节点，即链表长度为x+y；
   接着分析当fast指针等于slow指针时，两个指针走的步数的关系，假设fast指针走了f步，slow指针走了s步，则有以下分析：

   因为slow每次走一步，fast每次走两步，因此有f = 2s (方程一);
   又因为两个指针都走了前x步，之后在环内重合，因此，重合时fast指针比slow指针多走了n圈环，即f = s + ny (方程二)；
   由方程式一和二可得：
   s = ny (方程三)
   f = 2ny (方程四)；

   又因为每个走到链表入口处的节点一定走了x步+ m圈环(即走x+m*y步)，其中m >= 0；
   由上述分析和方程三可知，若想让slow节点到达环的入口节点，则使slow节点再走x步即可(即s = x + n * y)；
   因此，可以通过使用一个新的指针ans从链表头节点开始，和当前的slow指针同时每轮移动1步，当slow和ans重合时，两指针同时指向了链表入口。

Code

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (true) {if (nullptr == fast || nullptr == fast->next) {return nullptr;}fast = fast->next->next;slow = slow->next;if (fast == slow) {break;}}ListNode* ans = head;while (ans != slow) {ans = ans->next;slow = slow->next;}return ans;}
};