RSS

PROGRAM TO DETECT THE PRESENCE OF A LOOP IN A LINKED LIST (FLOYD’S CYCLE FINDING ALGORITHM)

03 Apr
// THIS PROGRAM CHECKS FOR THE PRESENCE OF A LOOP IN A LINKED LIST (FLOYD'S CYCLE FINDING ALGORITHM)

#include <iostream>

using namespace std;

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

bool looppresent(node *start);

int main()
{
    node *start;
    int i = 2;
    char wish = 'Y';
    start = new node;
    node *ptr;

    cout<<"Node 1: ";
    cin>>start->info;
    start->next = NULL;

    ptr = start;

    do
    {
        cout<<"\nNode "<<i<<": ";
        node *temp = new node;
        ptr->next = temp;
        ptr = temp;
        cin>>ptr->info;
        cout<<"\nContinue ??\n";
        cin>>wish;
        i++;
    }
    while(wish == 'Y' || wish == 'y');
    ptr->next = NULL;

    //uncomment the below line if you want to add a loop
    //ptr->next = start->next;

    if(looppresent(start) == true)
    {
        cout<<"\n Loop is present in the linked list\n\n";
    }
    else
    {
        cout<<"\n The linked list is loop free\n";
    }

    return 0;
}

bool looppresent(node *start)
{
    node *first, *second;
    first = second = start;
    second = first->next->next;

    while(first != NULL && second != NULL && first != second)
    {
        first = first->next;
        if(second->next == NULL || second ->next ->next == NULL)
            return false;
        second = second->next->next;
    }

    if(first == second)
        return true;
    else
        return false;
}

Advertisements
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: