Finding length of loop in linked list in C++

This article discusses an algorithm and hence a program in C++ for finding the length of a loop in a linked list. The algorithm used is an extension to one that is used to check the presence of a loop in a linked list.

Find the length of a loop in a linked list in C++

The problem is to find the length of a loop – if present in a linked list – and return its value. The algorithm we may employ to arrive at a solution is to use Floyd’s Cycle Finding Algorithm, otherwise called the Hare and Tortoise algorithm.

 

Floyd’s Cycle Finding Algorithm

This algorithm uses two pointers increments at different speeds, to be specific, one incrementing in single steps (the slow pointer – Tortoise), and the other incrementing in double steps ( the fast pointer – Hare).

 

The linked list is traversed by both these pointers from the head pointer. If both these pointers meet at some node, we may conclude that there is a loop in the list under consideration. We break out of the loop if any of these conditions if one of the pointers point to NULL ( in case there is no loop ), or if both pointers meet ( in case if there is a loop ).

 

Now, have a look at the code.

 

Code

#include<iostream>
using namespace std;
int counter = 0;

struct node
{
    int number;
    node *next;
};

node *start = NULL, *temp = NULL;

void display()
{
    int i=0;

    node *tempPtr = start;

    while(i<counter + 1)
    {
        cout<<tempPtr -> number<<" -> ";
        tempPtr = tempPtr -> next;
        i++;
    }

}

node *create(int num)
{
    node *newnode = new node;
    newnode -> number = num;
    newnode -> next = NULL;
    return newnode;
}

void insertNode(int value)
{
    if(start == NULL)
    {
        start = temp = create(value);
    }

    else
    {
        temp -> next = create(value);
        temp = temp -> next;
    }
}

int main()
{
    node *ptr = NULL;

    int num;
    int loop_found = 0;
    int i = 0;
    int loop_begin_index = 2;
    char ch;

    do
    {

        cout<<"ENTER NUMBER : ";
        cin>>num;

        insertNode(num);
        counter++;

        cout<<"DO YOU WANT TO CONTINUE ?";
        cin>>ch;

    }while(ch == 'y' || ch == 'Y');

    ptr = start;

    while(i < loop_begin_index-1)
    {
        ptr= ptr -> next;
        i++;
    }

    temp -> next = ptr;     /* For loop example    */
    //temp -> next = NULL;  /* For no-loop example */

    cout<<endl<<"LINKED LIST : ";
    display();
    cout<<endl;


    node *hare = start;
    node *tortoise = start;

    while(hare != NULL && hare -> next != NULL)
    {
        hare = hare -> next -> next;
        tortoise = tortoise -> next;
        if(tortoise == hare)
        {
            loop_found = 1;
            break;
        }
    }

    tortoise = tortoise -> next;
    counter = 1;

    while(tortoise != hare)
    {
        tortoise = tortoise -> next;
        counter++;
    }

    if(loop_found == 0)
    {
        cout<<"NO LOOP ";
    }

    else
    {
        cout<<endl<<"LENGTH OF LOOP : "<<counter;
    }

    return 0;
}

 

Output

ENTER NUMBER : 1
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 2
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 3
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 4
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 5
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 6
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 7
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 8
DO YOU WANT TO CONTINUE ?n

LINKED LIST : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 2 ->

LENGTH OF LOOP : 7

 

Analysis

We first create a linked list. There may or may not be a loop. In the code given above, we take the case of a list with a loop. You can also try one without a loop – comment line number 72, and uncomment line number 73.

 

We first traverse through the list starting from the ‘start’ pointer with both the tortoise and hare pointers. We set a condition:

hare != NULL && hare -> next != NULL

For the while loop as an exit condition in case, there is no loop in the linked list. ‘hare’ and ‘hare->next’ both are considered since the list may have an odd or even number of nodes. We may even try an exit condition using the tortoise pointer as:

tortoise != NULL

However, this would lead to unnecessary traversals, since the hare would have already reached the end in half the number of increments.

 

We break out of the loop when the ‘hare’ pointer meets the ‘tortoise’ pointer- in case there is a loop in the list – otherwise when we meet the above-said condition of reaching the end of the list. Once we break out of the loop, with the loop detected, we set the hare pointer at the point where both the pointers met, and continue incrementing the tortoise pointer. Also, we set a counter to count the number of nodes. The number nodes counted till the pointers meet again is the required length of the loop.

We could even stand the tortoise pointer and increment the hare pointer. The condition is to increment the pointer by just one. This is why we used the tortoise pointer, as this does not change its behavior.

 

Leave a Reply

Your email address will not be published. Required fields are marked *