Checking of loop in a LINKED LIST

Checking of LOOP in a LINKED LIST

There are many approaches to solve this type of problem. One easiest way is to use the traditional concept like, first create an array, while traversing the list for checking loop then add each new node address on that array, and while adding we have to check every time if there is any duplicate address previously present or not if present there is loop otherwise no loop.

On this concept time complexity as well as space complexity both are large. Space complexity is large because here we are using one extra array for storing address, and time complexity because while adding an address every we have to traverse the whole array. For this time complexity isO(n2).

The second approach which I have used over here is a concept of physics. We all know that in a circular path if there is two object running in two different speed then there will be an instance when faster object will cross slower object. Here also we have used same concept ,here we take two node type pointer one is slow another one is fast. while traversing every time slow will increase by one node whereas fast will increase by two nodes and there will be an instance when both the pointer will meet if there is a loop ,if there is no loop then there will be a time when both the pointer will reach at the end of the list means NULL value

  

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

struct node    //structure of node

{

int data;          //data

struct node *next; //pointer of next node

};

struct node *head;

void main()

{

int i,flag=0;

struct node *temp;

struct node *temp1;

struct node *slow,*fast;//pointer for checking loop in a linked list

clrscr();

head = NULL;

for(i=0;i<10;i++) //cre4ating 10 node inserting at head

{

temp=(struct node *)malloc(sizeof(struct node));

temp->data=i+1;   //storing data

temp->next=head;  //pointing to the head node

head= temp;       //current node become head

}

temp1=head;

printf("befor loop :=");

while(temp1!=NULL)  //printing of all the node

{

printf("%d -> %d,\n",temp1->data,temp1->next->data);

temp1=temp1->next;

}

temp=head;

for(i=1;i<=5;i++) //externally creating a loop from node 5 to node 3

{

if(i==3)

{

temp1=temp;//while traversing storing the address of node 3

}

if(i==5)

{

temp->next=temp1;//copying address of node 3 in next pointer of node 5

}

temp=temp->next;

}

slow=head;//at start both the node are pointing to head

fast=head;

while(1)

{

slow=slow->next;//every time slow is increased by 1 node

fast=fast->next->next; //and fast is increased by 2 node

if(slow==fast) //true if there is loop

{

flag=1; //if there is a loop there will be an instance

//when slow anf fast object meet each other(crossing point)

break;

}

if(slow==NULL || fast==NULL)//if there is no loop then there will

    //be a time when both the node will reach

    //at the end of the list

{

flag=0;

break;

}

}

if(flag==1)

{

printf("\nThere is loop");

}

else

{

printf("\nThere is no loop");

}

getch();

}

Source Code: =https://github.com/shouvik126/example1

OUTPUT: =