CODEWITHSUNDEEP
cdata-structureslinked-list
instance
instance

Reputation: 1374

What if we change the number of hops of slow and fast pointer while finding the loop in a linked list

To find a loop in a linked list, we simply take two pointers slow and fast.

slow = head->next;
fast = head->next->next;

    while(slow != fast)
    {
        slow = head->next;
        fast = head->next->next;
        if(!slow || !fast)
        {
            cout<<"   No Loop ";
            break;
        }
    }

This way we can find the loop in linked list. Now what will be the repercussions, if i make slow pointer jump 2 nodes and fast jump 3 nodes or slow 3 nodes and fast 4 nodes......

I tried this in my code but everytime getting correct result. Could anybody please shed some light on this? ALso, one more thing instantly came to my mind was that we can get into an infinite loop with some particular choice of slow and fast pointer, but couldn't find one.

Upvotes: 4

Views: 209

Answers (1)

user3721704
user3721704

Reputation:

Change in number of hopes will only diminish cycle finding process. It wouldn't put you in infinite loop.

Either the number of nodes will be odd or even. So

Case A : For odd number of nodes (3 or 5 nodes for example)
Case B : For even number of nodes (2 or 4nodes for example)

see test sample scenario : Generalized solution is : GCD(slow's movement,fast's movement) will be the point where nodes will colloidal in time inside loop.

  1. (even, odd)slow moves by 2 and fast by 3 : It is caught in both the cases A and B. Because in case A fast will keep coming back to the selected nodes(every third node) while slow will change alternatively.

  2. (odd, even)slow moves by 3 and fast by 4 : It is caught in both the cases A and B. Because in case A fast will keep coming back to every fourth node and slow at every third. this way they are supposed to collide on coming 12th position in loop.

  3. (odd, odd)slow moves by 1 and fast by 3 : It is caught in both the cases A and B. GCD of both is 3, so they are supposed to meet at upcoming 3rd node from their start.

  4. (even, even)slow moves by 2 and fast by 4 : It is caught in both the cases A and B. Same reason.

Upvotes: 3

Related Questions