# Detect and Remove Loop in a Linked List

That is one of an interesting problem, detect loop in linked list and if loop exists then remove this loop. We can solve this problem in many ways. But first analysis the problem.

Assume that linked list are contain N element and linked list last node are connect to any one of those. Here our goal is to detect loop and remove loop to careful without lost any node. See this example.

In this example last node of linked list is connect to second node. Which are create a loop. Note that we are initial no information about linked list loop created node and its position. There is possible last node is connect any of existing linked list node.

We can easily solve this problem using recursion. Here given code implementation process.

``````//C Program
//Detect and Remove Loop in a Linked List
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
int data;
struct Node*next;
};

//insert Node element
{
//Create dynamic node
struct Node*node=(struct Node*)malloc(sizeof(struct Node));
if(node==NULL)
{
printf("Memory overflow\n");
}else
{
node->data=value;
node->next=NULL;
{
}else
{
//find last node
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=node;
}
}
}
//Display element of Node
void display(struct Node*temp)
{

if(temp==NULL)
{
}
while(temp!=NULL)
{
printf("%d  ",temp->data);
temp=temp->next;
}
}

//Delete loop
struct Node* delete_loop(struct Node*temp)
{
//base condition
if(temp==NULL || temp->next==NULL ) return NULL;

struct Node *hold=temp->next;

temp->next=NULL;//important to break recursion

temp->next=delete_loop(hold);

return temp;

}
{
{

return;
}

int status=0;

while(second!=NULL && second->next!=NULL &&
second->next->next!=NULL)
{
first=first->next;
second=second->next->next;

if(first == second)
{
//loop is found
status=1;
break;
}
}

//Test Case
if(status==1)
{

printf("Loop Found\n");
//when loop exist
//Then delete loop

printf("After Remove Loop\n");
}
else
{
printf("\nLoop not exist\n");
}
}
int main()
{
//create node pointer

//Create loop

//case 2
return 0;
}
``````

#### Output

``````Loop Found
After Remove Loop
1  2  3  4  5  6  7
Loop not exist``````
``````//C++ Program
//Detect and Remove Loop in a Linked List
#include <iostream>
using namespace std;

//Create structure of linled list node
struct Node
{
int data;
struct Node*next;
};
{

public:
void insert(int);
void display();
void detect_loop();
Node* delete_loop(Node*);
};
{
}

//insert node at end of linked list
{
//Create dynamic node
struct Node*node=new Node;
if(node==NULL)
{
cout<<"Memory overflow\n";
}else
{
node->data=value;
node->next=NULL;
{
//base condition
}else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=node;
}
}
}
//Delete loop
struct Node* LinkedList :: delete_loop(struct Node*temp)
{
//base condition
if(temp==NULL || temp->next==NULL ) return NULL;

struct Node *hold=temp->next;

temp->next=NULL;//important to break recursion

temp->next=delete_loop(hold);

return temp;

}
{
{

return;
}

int status=0;

while(second!=NULL && second->next!=NULL &&
second->next->next!=NULL)
{
first=first->next;
second=second->next->next;

if(first == second)
{
//loop is found
status=1;
break;
}
}

//Test Case
if(status==1)
{

cout<<("Loop Found\n");
//when loop exist
//Then delete loop

cout<<("After Remove Loop\n");
display();
}
else
{
cout<<("\nLoop not exist\n");
}
}
//Display all node value in linked list
{
{
}
else
{

while(temp!=NULL)
{
//print node value
cout<<temp->data<<" ";

temp=temp->next;
}
}

}
int main(){

//create object

obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(4);
obj.insert(5);
obj.insert(6);
obj.insert(7);

//Create loop

obj.detect_loop();
//case 2
obj.detect_loop();

return 0;
}``````

#### Output

``````Loop Found
After Remove Loop
Linked List : 1 2 3 4 5 6 7
Loop not exist
``````
``````//Java Program
//Detect and Remove Loop in a Linked List
public class My_SLL
{

public class Node
{
int data;
Node next;
}
//Class constructors
My_SLL(){
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node=new Node();
node.data=value;
node.next=null;
else{
//Find lase node
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=node;
}

}
public void display()
{
{
while(temp!=null)
{
System.out.print("  "+temp.data);
temp=temp.next;
}
}else
{
}
}
//Delete loop
public Node deleteLoop(Node temp)
{
//base condition
if(temp==null || temp.next==null ) return null;

Node hold=temp.next;

temp.next=null;//important to break recursion

temp.next=deleteLoop(hold);

return temp;

}
public void detectLoop()
{
{

return;
}

boolean status=false;

while(second!=null && second.next!=null &&
second.next.next!=null)
{
first=first.next;
second=second.next.next;

if(first == second)
{
//loop is found
status=true;
break;
}
}

//Test Case
if(status==true)
{

System.out.println("Loop Found");
//when loop exist
//Then delete loop

System.out.println("After Remove Loop");
display();
}
else
{
System.out.println("Loop not exist\n");
}
}

public static void main(String[] args)
{

My_SLL obj=new My_SLL();

obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(4);
obj.insert(5);
obj.insert(6);
obj.insert(7);

obj.detectLoop();

//Create loop

obj.detectLoop();
}
}``````

#### Output

``````Loop not exist

Loop Found
After Remove Loop
Linked list Element :  1  2  3  4  5``````
``````# Python Program
# Detect and Remove Loop in a Linked List
class Node:

def __init__(self,data):
self.data=data
self.next=None

class MySLL:

def __init__(self):
self.status = 1
self.checker = None

#insert new node to linked list
def insert(self,data):

node=Node(data)

else:

while temp.next!=None:
temp=temp.next

temp.next=node

def display(self):

return

while(temp!=None):

print(temp.data,end="  ")

temp=temp.next

#Delete loop
def deleteLoop(self, temp):
#Base condition
if(temp==None or temp.next==None ):
return None

hold=temp.next

temp.next=None#important to break recursion

temp.next=self.deleteLoop(hold)

return temp

def detectLoop(self):

return

status=False

while(second!=None and second.next!=None and second.next.next!=None):

first=first.next
second=second.next.next

if(first == second):
#loop is found
status=True
break

#Test Case
if(status==True):

print("Loop Found")
#when loop exist
#Then delete loop

print("After Remove Loop")
self.display()

else :
print("\nLoop not exist")

def main():

#Create object
obj=MySLL()

obj.insert(1)
obj.insert(2)
obj.insert(3)
obj.insert(4)
obj.insert(5)
obj.insert(6)
obj.insert(7)

#Create loop

obj.detectLoop()
#case 2
obj.detectLoop()

if __name__=="__main__":
main()``````

#### Output

``````Loop Found
After Remove Loop
1  2  3  4  5  6  7
Loop not exist
``````
``````//C# Program
//Detect and Remove Loop in a Linked List
using System;

public class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public class MySLL
{

//This are using to control execution process

//Class constructors
MySLL()
{

}
//insert element
public void insert(int value)
{
//Create  node
Node node=new Node(value);

{
}
else
{
//find last node
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=node;
}
}

public void display()
{
{

while(temp!=null)
{
Console.Write("  {0}",temp.data);

temp=temp.next;
}
Console.WriteLine();
}else
{
}
}
//Delete loop
public Node deleteLoop(Node temp)
{
//base condition
if(temp==null || temp.next==null ) return null;

Node hold=temp.next;

temp.next=null;//important to break recursion

temp.next=deleteLoop(hold);

return temp;

}
public void detectLoop()
{
{

return;
}

Boolean status=false;

while(second!=null && second.next!=null &&
second.next.next!=null)
{
first=first.next;
second=second.next.next;

if(first == second)
{
//loop is found
status=true;
break;
}
}

//Test Case
if(status==true)
{

Console.WriteLine("Loop Found");
//when loop exist
//Then delete loop

Console.WriteLine("After Remove Loop");
display();
}
else
{
Console.WriteLine("Loop not exist");
}
}

public static void Main(String[] args) {

MySLL obj=new MySLL();

obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(4);
obj.insert(5);
obj.insert(6);
obj.insert(7);

//Create loop

obj.detectLoop();
//case 2
obj.detectLoop();

}
}``````

#### Output

``````Loop Found
After Remove Loop
1  2  3  4  5  6  7
Loop not exist
``````
``````<?php
//Php program
//Detect and Remove Loop in a Linked List
class Node
{
public \$data;
public \$next;
function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
{

function __construct()
{
}
/*
* Append the Given data value at end of linked list
* Fun : insert
* Parm: data value
*@return None
*/
public function insert(\$data)
{
\$newNode=new Node(\$data);
{
}else
{
//find last node of linked list
while(\$temp->next!=NULL)
{
\$temp=\$temp->next;
}
\$temp->next=\$newNode;
}
}
//Display all inserted node in linked list
public function display()
{
{
}
else
{
while(\$temp!=NULL)
{
//display node value
echo "  ".\$temp->data;
\$temp=\$temp->next; //visit to next node
}
}
}
//Delete loop
public function delete_loop(\$temp)
{
//base condition
if(\$temp==NULL || \$temp->next==NULL ) return NULL;

\$hold=\$temp->next;

\$temp->next=NULL;//important to break recursion

\$temp->next=\$this->delete_loop(\$hold);

return \$temp;

}
public function detect_loop()
{
{

return;
}

\$status=0;

while(\$second!=NULL && \$second->next!=NULL &&
\$second->next->next!=NULL)
{
\$first=\$first->next;
\$second=\$second->next->next;

if(\$first == \$second)
{
//loop is found
\$status=1;
break;
}
}

//Test Case
if(\$status==1)
{

echo ("Loop Found\n");
//when loop exist
//Then delete loop

echo ("After Remove Loop\n");
\$this->display();
}
else
{
echo ("\nLoop not exist\n");
}
}
}
function main()
{
//Make a object of LinkedList class

/*
*Insert following nodes in linked list
*/
\$obj->insert(1);
\$obj->insert(2);
\$obj->insert(3);
\$obj->insert(4);
\$obj->insert(5);
\$obj->insert(6);
\$obj->insert(7);

//Create loop

\$obj->detect_loop();
//case 2
\$obj->detect_loop();
}
main();
?>``````

#### Output

``````Loop Found
After Remove Loop
Linked List :  1  2  3  4  5  6  7
Loop not exist
``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.