Concise O(n) solution by using C++ with Detailed Alogrithm Description


  • 143
    N

    Alogrithm Description:

    Step 1: Determine whether there is a cycle

    1.1) Using a slow pointer that move forward 1 step each time

    1.2) Using a fast pointer that move forward 2 steps each time

    1.3) If the slow pointer and fast pointer both point to the same location after several moving steps, there is a cycle;

    1.4) Otherwise, if (fast->next == NULL || fast->next->next == NULL), there has no cycle.

    Step 2: If there is a cycle, return the entry location of the cycle

    2.1) L1 is defined as the distance between the head point and entry point

    2.2) L2 is defined as the distance between the entry point and the meeting point

    2.3) C is defined as the length of the cycle

    2.4) n is defined as the travel times of the fast pointer around the cycle When the first encounter of the slow pointer and the fast pointer

    According to the definition of L1, L2 and C, we can obtain:

    • the total distance of the slow pointer traveled when encounter is L1 + L2

    • the total distance of the fast pointer traveled when encounter is L1 + L2 + n * C

    • Because the total distance the fast pointer traveled is twice as the slow pointer, Thus:

    • 2 * (L1+L2) = L1 + L2 + n * C => L1 + L2 = n * C => L1 = (n - 1) C + (C - L2)*

    It can be concluded that the distance between the head location and entry location is equal to the distance between the meeting location and the entry location along the direction of forward movement.

    So, when the slow pointer and the fast pointer encounter in the cycle, we can define a pointer "entry" that point to the head, this "entry" pointer moves one step each time so as the slow pointer. When this "entry" pointer and the slow pointer both point to the same location, this location is the node where the cycle begins.

    ================================================================

    Here is the code:

    ListNode *detectCycle(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return NULL;
        
        ListNode *slow  = head;
        ListNode *fast  = head;
        ListNode *entry = head;
        
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {                      // there is a cycle
                while(slow != entry) {               // found the entry location
                    slow  = slow->next;
                    entry = entry->next;
                }
                return entry;
            }
        }
        return NULL;                                 // there has no cycle
    }

  • 0
    Y

    Thank you for sharing your algorithm with details


  • 0
    A

    Awesome explanation. Thanks!!


  • -1
    B

    awesome explanation. but not exactly right


  • 6
    M

    The total distance of the slow pointer traveled when encounter is actually L1 + L2 + n1C. 2(L1+L2+n1C) = (L1+L2+n2C) => L1= (n2-2*n1)C - L2 = n3C - L2. So the algorithm is still right. When this "entry" pointer and the slow pointer both point to the same location, this location is the node where the cycle begins.


  • 0
    B

    Agree. There is no guarantee that the slow pointer walked less than a circle. So need to + n1C.


  • 0
    A

    nice explanation, thanks!


  • 0
    C

    Brilliant!! Implement an algorithm is good, prove an algorithm is cool!


  • -1
    C

    Thanks very much for sharing! Almost the same with you, just fewer lines of code.

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

  • 2
    D

    @bin15 It looks like n1==0 because the worst case is: the slow pointer just arrives at the entrance of the circle, and the fast pointer is ahead of it by one step. Even in this case, the fast pointer can still catch slow pointer before slow pointer finishes one circle.

    Formally, if circle has n nodes, in the worst case the slow pointer is at position 1, the fast pointer is at position 2. When slow pointer reaches the nth node, it walked n-1 steps. So the fast pointer walked 2(n-1) steps, which means the fast pointer at least reached position 2 + 2(n-1) = 2n, which is at least n position after mod.


  • 0
    H

    @bin15 of course the slow pointer would walk less than a circle. the fast pointer is behind the slow one less one circle.


  • 3
    Y

    @bin15 I've seen several explanations and now I've realized that for this way of solving, it is guaranteed that slow pointer won't travel more than 1 full circle, and that the fast pointer will only travel exactly one more circle than slow pointer before meeting slow pointer again.
    The key observation is that the speed of fast pointer is 2 times than that of slow pointer. Think of it this way: if two runners start running on a circle at the same time, fast runner is twice the speed of the slow runner, then when the slow runner finish the first circle, the fast runner will just finish second circle, and this is the first time they meet after starting. In this problem, when slow pointer start at the "entry point", the fast pointer is at the same point or ahead of the slow pointer, so you can apply the runners' situation here: they will meet before slow pointer start its second circle.


  • 1
    Y

    @yuex So actually with the observation, you don't even need the "n", the equation is simply: 2(L1 + L2) = L1 + L2 + C, leading to L1 = C - L2.


  • 0
    4
    This post is deleted!

  • 0
    G

    Finally,i understood


  • 0
    A

    There is an error in your conclusion.

    It should be stated like that:
    "It can be concluded that the distance between the head location and entry location is
    equal to the sum of 1) the distance between the meeting location and the entry location along the
    direction of forward movement; 2) and a multiple of length of C)."


  • 0
    S

    Thanks! Excellent!


  • 0
    P

    @meredithzou thank you


  • 0
    C

    you are very clever!


  • 0
    A

    awesome method!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.