Linked List in C – Detect/Find Loop

Linked List in C - Detect or Find Loop.png

Linked List in C – Detect/Find Loop

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

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
  5. Else – Loop Not 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
//		Loop Not Found
//
//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;
};

struct node *head=NULL;
//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
    	struct node *slow_pointer=head;
    	struct node *fast_pointer=head;	
    	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;
        		}		
    	}
    	printf("\nLoop Not Found");
}

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
    	struct node *temp=head;
    	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

    	head=one;
    	//head pointer points to node one of the linked list

    	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 ]

Leave a Reply