12ms C++ solution and explanation of Floyd Cycle algorithm


  • 6
    D

    Finding start of the cycle in a linked list, if any exists :

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

    So this works because, if there exists a cycle in the linked list, the fast and slow pointer will surely meet atleast once, when the fast pointer has traversed an entire loop at least once.

    So, let us say,

    • the straight path before the cycle in the linked list is of length :
      x
    • the place where slow and fast meet is y distance from the start of
      the cycle
    • there are z steps left to reach the start of the cycle again from the
      meeting place

    slow pointer :

    travels x + y distance to meet the fast pointer

    fast pointer :

    travels (x + y + (z + y)) distance to meet the slow pointer [reason : (x + y) to reach the meeting place, but it again goes around the loop and meets it on its way back, so (z + y) steps are needed]

    But the fast pointer travels at speed 2 times that of slow pointer

    So, 2(x + y) = (x + 2y + z)
    => x = z

    This is an extremely powerful result, which means that the distance between the start of the linked list and the start of the cycle, x is equal to the distance between the start of the cycle and the meeting point, z.

    So, if slow walks at a step of 1 each time from the head of the list, and if fast walks at a pace of 1 step each time. They are to meet at the start of the cycle, because slow will travel x steps and fast will travel z steps.

    Follow up question :

    Size of the loop :

    int lengthCycle(ListNode *head) {
            ListNode *slow = head, *fast = head;
            bool flag = false;
            while(fast && fast->next && fast->next->next){
                fast = fast->next->next;
                slow = slow->next;
                if(fast == slow){
                    flag = true;
                    break;
                }
            }
            if(!flag)
                return 0;
            int steps = 1;
            fast = fast->next;
            while(slow != fast){
                fast = fast->next;
                steps ++;
            }
            return steps;
        }

Log in to reply
 

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