Linked List Cycle II

 //Let x be: Length of head to cycle started node
//Let y be: Length of the cycle

//Let hare run two steps while tortoise runs one step
//while both of them entered the cycle, the hare is definitely to overlap the tortoise at some node, we define it as m:
//The hare totally runs: x + ky + m The tortoise totally runs: x + ty + m Thus, (x + ky + m)/(x + ty + m) =2, then ky = 2ty + x + m. we have (x + m) mod y = 0 We can conclude //that if the hare run more x steps, it will reach the cycle's starting node.


ListNode *detectCycle(ListNode *head) {
    if (head == NULL) return NULL;
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;
    }
    if (fast == NULL || fast->next == NULL) return NULL;
    fast = head;
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}