why we use two conditions in head!=nullptr && head->next != nullptr in floyd cycle detection algo-CodePudding

i want to know that why we use two conditions i am confused.. while head and head->next are not equal to null which means head and head's next will point to null ho is that possible

int detectCycle(Node *& head)
{
   Node * fast = head;
   Node * slow = head;
   while(fast!=nullptr && fast->next!=nullptr)   // i am confused in these two conditions
   {
     slow = slow->next;
     fast = fast->next->next;
     if(fast == slow)
        return 1;
   }
    return false;
}

CodePudding user response：

This condition

while(fast!=nullptr && fast->next!=nullptr)

means that the current pointer fast and its data member next that is a pointer to the next node are not null pointers. If so you may write

 fast = fast->next->next;

And the function should be declared like

bool detectCycle(Node *& head)
^^^^

CodePudding user response：

while head and head->next are not equal to null which means head and head's next will point to null ho is that possible

From the code presented, I guess you mean fast where you wrote head.

If fast is null then fast!=nullptr evaluates to false. In that case it would produce undefined behavior to evaluate fast->next, but that is not an issue because the && operator has short-circuiting behavior. That is, if the left operand of an && operator evaluates to false, then the right operand is not evaluated.

Thus the while condition is safe to evaluate, and it evaluates to true if and only if neither fast nor fast->next is a null pointer.

Supposing that head is a pointer to the head node of a linked list, the code seems to assume that the last node can be recognized by having a next pointer whose value is null. This is a very common paradigm, so it is absolutely reasonable to think that as the fast pointer is advanced through the list (two links at a time), it will eventually become the case that either it or its successor will be the last node, and therefore have a null next pointer.

If that happens, then the list is proven not to loop. If the list does loop, however, then it will eventually be the case that slow, which advances only one link at a time instead of two, will point to the same node that fast does. When that is detected, the list is known to loop.