Determining if a linked list loops using only two pointers (idea)

This is a perfect example of a case where the common convention of only ever returning from one point in the function greatly complicates the code.

bool CheckForLoop(Node *head)
{
    Node *node1 = head, *node2 = head;

    while (node2 && node2->next)
    {
        node1 = node1->next;
        node2 = node2->next->next;

        if (node1 == node2)
            return true;
    }

    return false;
}

This is sufficient checking because:

• node1 follows in the path of node2, so if node2 is valid, node1, which refers to an earlier element of the list than node2, must also be valid.
• node1 will never be set to NULL because if the list only has one element, the loop will never execute, and if the list has 2 or more elements, node2 or node2->next will become NULL first.
• If node2 is the last node in the list, then the while condition will evaluate to false.
• If the node after node2 is the last node in the list, then node2 will be assigned a NULL reference. This will never be equal to node1 in the if condition, because node1 is never set to NULL.