Detecting a Loop in a Singly Linked List

The naive approach requires O(N^2) time and O(N) space. Basically you store all visited nodes, and compare each of them while traversing each node.

Hint: 
The best approach uses only O(N) time and O(1) space.

Solution:

The best solution runs in O(N) time and uses O(1) space. It uses two pointers (one slow pointer and one fast pointer). The slow pointer advances one node at a time, while the fast pointer traverses twice as fast. If the list has loop in it, eventually the fast and slow pointer will meet at the same node. On the other hand, if the loop has no loop, the fast pointer will reach the end of list before the slow pointer does.

bool hasLoop(Node *head) 
{
    Node *slow = head, *fast = head;

    while (slow && fast && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;    
        
        if (slow == fast)
            return true;
    }
    return false;
}