Linked List Cycle II

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:

解题方法：

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;
    }
};