Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
思路
其实还有更简单的方法，在《Cracking the Coding Interview》上有提到。通过数学计算可以推导出来，用快行指针的方法判断出环后，可以不用计算环大小，把快指针变慢然后放到链头上，两个指针继续走到相碰就剩入口了。
分为三步：判断环，计算环的大小，找到入口
判断环就是老一套，用2倍速指针就行，这个之前的题目里头有；
计算环的大小k，环的大小么，刚才相碰的地方找个指针绕圈圈走。记个数，再碰到相遇地点就是环大小了；
找到入口后，我们有两个普通速度的指针pA,pB，让其中一个pA先往前走k步，然后两个一起开始挪动，可以知道，如果pA与pB又相遇了，那相遇点就是环的入口了。此时pA比pB刚好多走了一整圈。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* meetingNode(ListNode* head){
//Find the meeting node
if(head == NULL)
return NULL;
ListNode* slow = head->next;
if(slow == NULL)
return NULL;
ListNode* fast = slow->next;
while(fast != NULL && slow != NULL){
if (slow == fast)
return slow;
slow = slow->next;
fast = fast->next;
if(fast != NULL)
fast = fast->next;
}
return NULL;
}
ListNode *detectCycle(ListNode *head) {
ListNode* meet = meetingNode(head);
if(meet == NULL)
return NULL;
//Get loop size
ListNode* temp = meet->next;
int count = 1;
while(temp != meet){
count++;
temp = temp->next;
}
//Pick one pointer at start, move `count` steps forward
temp = head;
meet = head;
while(count > 0){
count--;
meet = meet->next;
}
//Find the cycle start
while(temp != meet){
temp = temp->next;
meet = meet->next;
}
return meet;
}
};
