Description:
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?
Link:
https://leetcode.com/problems/linked-list-cycle-ii/description/
解题方法：
image.png
用快慢指针可以得知链表是否有环。
如上图所示，假如链表起点为X，环入口为Y，快慢指针第一次在Z点相遇。X->Y = a，Y->Z = b，Z->Y = c。
则有: 2(a + b) = a + n(b + c) + b
即：a = n(b + c) - b
也就是说，如果用两个指针分别从X和Z往下走，一定会在Y点相遇，也就是所求的环的起点。
Time Complexity：
O(N)
完整代码：
class Solution
{
public:
ListNode *detectCycle(ListNode *head)
{
ListNode* slow = head;
ListNode* fast = head;
do
{
if(fast == NULL || fast->next == NULL)
return NULL;
slow = slow->next;
fast = fast->next->next;
}
while(fast != slow);
slow = head;
while(slow != fast)
{
if(slow == NULL || fast == NULL)
return NULL;
slow = slow->next;
fast = fast->next;
}
return fast;
}
};
