泰安市住房和城乡建设委员会网站/十大软件培训机构

题目链接：142. 环形链表 II
本题目是141.环形链表I的升级版，在I仅判断是否有环的基础上，需要求解入环节点。核心其实是数学推导。
仍然是快慢指针的思路，假设入环的距离是a，入环点到相遇点的距离是b，相遇回到入环的距离是c。
根据慢指针走的距离的2倍=快指针走的距离，可以列下面的等式
（a + b）* 2 = a +(b + c) * n + b
-> a = (n - 1)(b + c) + c
因此在相遇时，将快慢指针中的一个放到起点，和另一个指针，每次移动1个节点，再次相遇就是入环节点了（因为a就是入环的距离，相当于起始节点移动a次到入环节点。（n -1）(b+c)就是走了n-1次环，刚好还有c的距离，就是相遇点绕n圈之后，再走个c个节点就会回到入环点。）

上面的距离等同于要走多少个节点，例如起始节点到入环节点距离为a，代表起始节点，移动a次就到入环节点。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {
public:ListNode *detectCycle(ListNode *head) {if (head == NULL) {return NULL;}   ListNode *f = head, *s = head;while (f->next != NULL && f->next->next != NULL) {f = f->next->next;s = s->next;if (f == s) {break;}}if (f->next == NULL || f->next->next == NULL) {return NULL;}f = head;while (f != s) {f = f->next;s = s->next;}return f;}
};