Find Cycle List Beginning Node

cycle.cpp

/**
 * Time: O(n)
 * Space: O(1)
 * 1. find list if exists cycle.
 * 2. 0 -> a(cycle s) -> b(cycle met) -> c(cycle s(e))
 *    slow = a + b + (b + c)n1, fast = a + b + (b + c)n2.
 *    slow * 2 = fast
 *    2a + 2b + 2*n1*(b + c) = a + b + n2*(b + c)  => a = (n2 - 2*n1) * (b + c) - b
 *    After meeting, so one start going from head and meanwhile slow start going, they will meet at cycle begin.
 **/

ListNode *detectCycle(ListNode *head) {
    if (!head) return NULL;
    ListNode *slow = head;
    ListNode *fast = head;

    bool flag = false;
    while(fast->next && fast->next->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            flag = true;
            break;
        }
    }
    if (!flag) return NULL;

    fast = head;
    while(fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

• leetcode142