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)
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.