Cycle Detection · Coding Gym

Solutions

An efficient solution is based on the “two pointers idiom”.

We traverse the list using two pointers that we’ll refer to as fast and slow. Our slow pointer moves forward 1 node at a time, and our fast pointer moves forward 2 nodes at a time. If at any point in time these pointers refer to the same object, then there is a loop; otherwise, the list does not contain a loop.

C++ implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int has_cycle(Node* head)
{
    if (!head)
       return 0;
    
    auto trailing = head;
    while (head)
    {
        head = head->next;
        if (head == trailing)
            return 1;
        trailing = trailing->next;
        if (head)
            head = head->next;
    }
    return 0;
}

Ptyhon implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def has_cycle(head):
    fast = head;
    
    while(fast != None and fast.next != None):
        fast = fast.next.next;
        head = head.next;
        
        if(head == fast):
            return True;
        
    return False;