Cycle (Loop) detection in a linked list

Given a linked list, find whether the linked list contains a loop or not. Write a program to Detect a loop in a linked list.

Example


Time Complexity: O(n)
Space Complexity: O(1)

Algorithm

Using tortoise and hare algorithm
1. Initialize two pointers named slow and fast, where slow moves one time and fast moves two times.
2. Till end of the linked list, if these pointers meet at any node then there is a loop in the linked list

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
	int data;
	LL *next;	
};


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

void makeLoop(struct LL **head)
{
	//makes a Loop
	struct LL *temp = *head;
	
	while(temp->next !=NULL)
		temp = temp->next;
	
	temp->next = (*head)->next->next->next;
	
}

bool isLoop(struct LL **head)
{
	struct LL *slow = *head , *fast = *head; //slow pointer moves at speed X , then fast moves at speed 2X
	//So if there is a Loop then obviously these pointers will meet sometime
	
	while(fast and fast->next != NULL)
	{
		if(fast == slow and fast != *head) //Loop within list
		{
			return true;
		}
		slow = slow ->next;
		fast = fast->next->next;
	}
	
	return false;
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}




int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,12);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	
	cout<<"Initial List is :-\n";
	display(&head);
	
	makeLoop(&head); //Comment this function to make the linked list linear again
	
	if(isLoop(&head))
		cout<<"\nList has a Loop within!!\n";
		
	else
		cout<<"\nList does not contain Loop!\n";
	
	return 0;
}
Try It


Next > < Prev
Scroll to Top