Coders Packet

Loop Detection in Linked List using C++

By G Ganga Jathin

Using Floyd's Algorithm in C++ language to detect loop or cycle in a Linked List which we build ourselves

We will be given a Linked List as an input and also any cycle if it's given, Then we run the detection algorithm (Floyd's Algorithm) to check if there is any loop in the  given Linked List

The main principle of the algorithm is that there two pointers that go through the entire Linked List one with twice the speed than the other, and check if either of them reaches NULL, if they reach that means there is no loop otherwise if they become equal that means loop exits and the program terminates

TNode *temp = head,*temp1 = head;
    while(temp != NULL && temp1 != NULL && temp1 -> next != NULL)
    {
        temp = temp -> next;
        temp1 = temp1 -> next -> next;
        if(temp == temp1)return 1;
    }

Here the temp pointer is the tortoise and the temp1 pointer is the hare in Floyd's Algorithm we discussed above which detects the loop efficiently.

 

Open the C++ IDE of your choice and run the program,
Enter the Linked List, position at which loop forms, it will display whether a loop exists or not

Download project

Reviews Report

Submitted by G Ganga Jathin (GangaJathin)

Download packets of source code on Coders Packet