Search code examples
while-looplinked-listandand

While loop in "Finding Middle of Linked List"

While writing a code for finding the the middle of the linked List. I encounter a problem where I am not able to understand why one one the snipper works while other does not. Snippet Working

        ListNode *slow = head, *fast = head;
        while (fast && fast->next)
            slow = slow->next, fast = fast->next->next;
        return slow;

Snippet not working

        ListNode *slow = head, *fast = head;
        while (fast->next && fast)
            slow = slow->next, fast = fast->next->next;
        return slow;

Now in my understading, since we have a "&&" condition, it'll go inside the loop only when both the conditions are met, yet, the second snippet fails on some test cases. Thanks in advance.

Solution

  • The && is a short-circuit operator, so that the second operand is only evaluated when the first operand evaluates to a truthy value.

    The correct code has this:

    (fast && fast->next)

    Which means that fast->next is only evaluated when fast is not a null pointer.

    Now take the the other code:

    (fast->next && fast)

    Here fast->next is evaluated first before having verified that fast is not a null pointer. If fast is a null pointer, this represents an invalid de-referencing and the program will have undefined behaviour.