CODEWITHSUNDEEP
algorithmdata-structures
Lotus
Lotus

Reputation: 13

floyd's cycle-finding algorithm while checks

P=head;
Q=head->next;
while( (p!=null) && (q!=null) )
{
    if(p==q) exit(0); // loop detected
    P=p->next;
    q=(q->next)?(q->next->next):q->next;
}

Floyd's Alogorithm

In the above code (asked in an exam), the question was to fill the while loop and the above was given as the solution

The while condition is p!=NULL AND q!=NULL but I have tried many test cases and found that q!=NULL suffices the algorithm but the answer is strictly p=!NULL AND q!=null

My question is when will ever the q!=null in the while condition create a problem and when is the p!=NULL ever needed?

NOTE: Since this is a algorithm based question please ignore the syntax problems...

Upvotes: 1

Views: 61

Answers (2)

Ami Tavory
Ami Tavory

Reputation: 76406

In principle, you're correct that it's possible to only check the "hare" and not "tortoise" (by you, q and not p) for being NULL, as if the list is acylic, p is never ahead of q.

The code in your question, though, besides that, has some minor problems. (It's annoying how it alternates between uppercase and lowercase, to begin with.) As wildplasser correctly notes, there's undefined behavior when head == NULL.

Here is a version utilizing your idea of checking only the hare:

p = q = head;
while(q != NULL) {
    if(p == q)
        return true;
    if(q->next == NULL)
        return false;
    p = p->next;
    q = q->next->next;
}
return false;

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308520

Since q is advancing along the list faster than p, it will always reach the end of the list first. The only way p will ever be null is if the list was empty to begin with.

The code is incorrect for an empty list, since it tries to access a null pointer. You can fix that easily:

P=head;
Q=head?head->next:null;

Upvotes: 0

Related Questions