# 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;
};

{
struct LL* curr=new LL;

curr->data=dataToBeInserted;
curr->next=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
}

//O(1) constant time
}

{
//makes a Loop

while(temp->next !=NULL)
temp = temp->next;

}

{
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;
}

{
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

cout<<"Initial List is :-\n";