leetcode-142.-环形链表-II
目录
leetcode 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;
}
};