Detect Loop in a Single Linked List

The Trivial solutions either took too long or eat more memory. Here is a classic well known appraoch the does constant space O(1) and 0(n) space. This is based of Floyd’s cycle-finding algorithm published in the Journal of ACM is his paper Non-Deterministic Algorithms in 1967. There are many variants and improvements to this original solution. These alogrithms can be used for finding cycles in different Data Strucutres. I will explain how it works when applied to Linked Lists

The idea is to use 2 pointers P1 and P2 intialized to the head. Then traverse the two pointers starting from the head, with P1 moving 1 node at a time and P2 moving 2 nodes at a time. If there is indeed a cycle, the nodes will meet inside the loop, otherwise they will reach the tail.

The code below is a simple straightforward illustration of this. There are ways to make this more efficient. I will discuss this in the next post.

bool LinkedList::IsLoopedTwoPointer1() {
 LNode* first=head;
 LNode* second=head;

 while(first && second &&
           first->next && second->next &&
           second->next->next)
{
first=first->next;
second=second->next->next;
if(first==second)
{
    cout < < "Found Loop" << endl;
    return true;
}
 }
 return false;

}