[LeetCode] Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Analysis:

Take two pointers, one of which moves one time faster than the other. That is, the slower moves at one node per time, the faster at two nodes per time. If there is a cycle, they will meet at some point P. Suppose the slower pointer has moved X nodes when they meet. The faster pointer has moved 2X. Suppose O is the offset between their starting points. 

If we get another pointer to move from head, and simultaneously the slower pointer moves from P. Both of them move one node per time. After around X steps, we hope they can meet at P again.  For P is in a cycle, that means before they meet at P, they already meet at the point where the cycle begins, let's call it B.

Suppose the starting point of the slower pointer is S from the head. The length of the cycle is C.

C = 2X + O - X = X + O;

To meet at P again, the new pointer should move X + S. Obviously:

X + S = X + O => S = O

Simply we can make S = O = 0. You can also try S = 1 which will give you the same answer.

Solution:

/**
 * 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 (NULL==head) return NULL;
        ListNode *slow = head,*fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) break;
        }
        if(fast == NULL || fast->next == NULL) 
            return NULL;
        while (slow != head) {
            slow = slow->next;
            head = head->next;
        }
        return head;
    }
};