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
用快慢指針可以得知鏈表是否有環(huán)盹兢。
如上圖所示，假如鏈表起點(diǎn)為X，環(huán)入口為Y惫谤，快慢指針第一次在Z點(diǎn)相遇絮吵。X->Y = a，Y->Z = b贡未，Z->Y = c讼昆。
則有: 2(a + b) = a + n(b + c) + b
即：a = n(b + c) - b
也就是說，如果用兩個(gè)指針分別從X和Z往下走其兴，一定會(huì)在Y點(diǎn)相遇顶瞒，也就是所求的環(huán)的起點(diǎn)。
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;
}
};
