.

# Linked List in C – Detect/Find Loop

## Linked List in C – Detect/Find Loop :

Loop in linked list is a situation where a node points to one of the previous node in the same linked list

Example:
Nodes: one->two->three->four->one->two->….
There are only four nodes in the linked list.
But the fourth node points to first node “one” which forms the loop.

Pseudo Code:

1. Use 2 Pointers
1. Pointer 1 – Fast Pointer
2. Pointer 2 – Slow Pointer
2. The fast pointer traversed twice the speed of slow pointer i.e. if slow pointer is traversed one node, the fast pointer should traverse two nodes
3. Check whether the slow pointer and fast pointer are pointing same location
4. If they are equal – Loop Found

If there is a loop in the linked list, the slow pointer and fast pointer will meet at some point of time

Source Code :

```#include<stdio.h>

//Program to detect loop in the linked list
//Loop in linked list is a situation where a node points to one of the previous node in the same linked list
//
//one->two->three->four->one->two->....
//There are only four nodes in the linked list
//But the fourth node points to first node "one" which forms the loop
//
//Pseudo Code
//	Use 2 Pointers
//		Pointer 1-Fast Pointer
//		Pointer 2-Slow Pointer
//		The fast pointer traversed twice the speed of slow pointer i.e. if slow pointer is traversed one node, the fast pointer should traverse two nodes
//	Check whether the slow pointer and fast pointer are pointing same location
//	If they are equal
//		Loop Found
//	Else
//
//If there is a loop in the linked list, the slow pointer and fast pointer will meet at some point of time

struct node
{
//Structure named node to store integer in variable data and a pointer variable which can store address location of next node
int data;
struct node *next;
};

//Declared as global variable since it is accessed by multiple functions

struct node* findloop()
{
//Function to detect whether loop is present in the linked list
while(fast_pointer!=NULL)
{
fast_pointer=fast_pointer->next;
//fast_pointer is traversed one node

if(fast_pointer!=NULL)
{
fast_pointer=fast_pointer->next;
//fast_pointer is traversed another node

slow_pointer=slow_pointer->next;
//slow_pointer is traversed one node
}

if(fast_pointer==slow_pointer)
{
//If there is a loop in the linked list, the slow pointer and fast pointer will meet at some point of time
printf("\nLoop Found");
return;
}
}
}

void print()
{
//This funtion is used to print the data in each of the node in the linked list
//Process of moving from one node to another node is called as traversing
printf("\nList:");
while(temp!=NULL)
{
printf("\n%d ",temp->data);
temp=temp->next;
}
}

int main()
{
struct node *one = (struct node*)malloc(sizeof(struct node));
struct node *two = (struct node*)malloc(sizeof(struct node));
struct node *three = (struct node*)malloc(sizeof(struct node));
struct node *four = (struct node*)malloc(sizeof(struct node));
//Four nodes are created

one->data=1;
one->next=two;

two->data=2;
two->next=three;

three->data=3;
three->next=four;

four->data=4;
four->next=two;

//one->two->three->four->one->two->....
//There are only four nodes in the linked list
//But the fourth node points to first node "one" which forms the loop

//print();
//Calling the print function will print the data in the nodes of the linked list infinitely

findloop();
//Calling the function findloop() to detect the presence of loop in the linked list

return 0;
}```

Output :

`Loop Found`

[ YOU MAY ALSO LIKE ]