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.

Detect and Remove loop

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
void insert(struct Node**head,int value)
{
  //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;
    if(*head==NULL)
    {
      *head=node;
    }else
    {
      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*temp)
{
  
  if(temp==NULL)
  {
    printf("Empty linked list");
  }
  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;

}
//Detecting loop of linked list
void detect_loop(struct Node*head)
{
  if(head==NULL)
  { 
    printf("Empty Linked List\n");

    return;
  }

  int status=0;

  struct Node *first=head, *second=head;

  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
    delete_loop(head);

    printf("After Remove Loop\n");
      //show linked list element
    display(head);
  }
  else
  {
     printf("\nLoop not exist\n");
  }
}
int main()
{
  //create node pointer
  struct Node*head=NULL;
  //insert element of linked list

  insert(&head,1);
  insert(&head,2);
  insert(&head,3);
  insert(&head,4);
  insert(&head,5);
  insert(&head,6);
  insert(&head,7);

  
   //Create loop
  head->next->next->next->next->next->next->next= head->next;
    
  detect_loop(head);
  //case 2
  detect_loop(head);
  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;
};
class LinkedList
{

  public:
  	Node*head;
    LinkedList();
    void insert(int);
    void display();
    void detect_loop();
    Node* delete_loop(Node*);
};
LinkedList::LinkedList()
{
  head=NULL;
}

//insert node at end of linked list
void LinkedList::insert(int value)
{
    //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }else
  {
    node->data=value;
    node->next=NULL;
    if(head==NULL)
    {
      //base condition
      head=node;
    }else
    {
      Node*temp=head;
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add newly node at last
      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;

}
//Detecting loop of linked list
void LinkedList :: detect_loop()
{
  if(head==NULL)
  { 
    cout<<("Empty Linked List\n");

    return;
  }

  int status=0;

  struct Node *first=head, *second=head;

  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
    delete_loop(head);

    cout<<("After Remove Loop\n");
      //show linked list element
    display();
  }
  else
  {
     cout<<("\nLoop not exist\n");
  }
}
//Display all node value in linked list
void LinkedList:: display()
{
  if(head==NULL)
  {
    cout<<"Empty linked list";
  }
  else
  {
    Node*temp=head;

    cout<<"Linked List : ";
    while(temp!=NULL)
    {
      //print node value
      cout<<temp->data<<" ";
      
      temp=temp->next;
    }
  }

}
int main(){
 
	//create object
	LinkedList obj;

	//insert element of 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.head->next->next->next->next->next->next->next= obj.head->next;
    
  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;
  }
  public Node head;
  //Class constructors
  My_SLL(){
    head=null;
  } 
  //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;
    if(head==null) head=node;
    else{
      Node temp=head;
      //Find lase node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      //add node
      temp.next=node;
    }
    
  }
  //display all Linked List elements
  public void display()
  {
    if(head!=null)
    {
      System.out.print("Linked list Element :");
      Node temp=head;
      while(temp!=null)
      {
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }else
    {
      System.out.println("Empty Linked list"); 
    }
  }
  //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;

  }
  //Detecting loop of linked list
  public void detectLoop()
  {
    if(head==null)
    { 
      System.out.println("Empty Linked List ");

      return;
    }

    boolean status=false;

    Node first=head,second=head;

    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
      deleteLoop(head);

      System.out.println("After Remove Loop");
        //show linked list element
      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.head.next.next.next.next.next.next.next= obj.head.next;
    
    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.head = None
    self.status = 1
    self.checker = None
   

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

      node=Node(data)

      if self.head==None:
        self.head=node
      else:
        temp=self.head

        while temp.next!=None:
          temp=temp.next
        
        #add node    
        temp.next=node

  #display element of linked list
  def display(self):

      if(self.head==None):
        print("Empty Linked List")
        return

      temp=self.head


      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

  
  #Detecting loop of linked list
  def detectLoop(self):
    if(self.head==None): 
      print("Empty Linked List ")

      return
  
    status=False

    first=self.head
    second=self.head

    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
      self.deleteLoop(self.head)

      print("After Remove Loop")
        #show linked list element
      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.head.next.next.next.next.next.next.next= obj.head.next.next
  
  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
	public Node head;

	//Class constructors
	MySLL()
	{
		this.head = null;
	
	} 
	//insert element
	public void insert(int value)
	{
		//Create  node
		Node node=new Node(value);

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


	//Display all Linked List elements
	public void display()
	{
		if(head!=null)
		{

			Node temp=head;

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

				temp=temp.next;
			}
			Console.WriteLine();
		}else
		{
			Console.WriteLine("Empty Linked list"); 
		}
	}
	//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;

	}
	//Detecting loop of linked list
	public void detectLoop()
	{
		if(head==null)
		{ 
			Console.WriteLine("Empty Linked List ");

			return;
		}

		Boolean status=false;

		Node first=head,second=head;

		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
			deleteLoop(head);

			Console.WriteLine("After Remove Loop");
			//show linked list element
			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.head.next.next.next.next.next.next.next= obj.head.next;

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

    public  $head;
    function __construct()
    {
        $head=NULL;
    }
    /*
    * 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); 
        if($this->head==NULL)
        {
            $this->head=$newNode;
        }else
        {
            $temp=$this->head;
            //find last node of linked list
            while($temp->next!=NULL)
            {
                $temp=$temp->next;
            }
            //add new node to last of linked list
            $temp->next=$newNode;
        }
    }
    //Display all inserted node in linked list
    public function display()
    {
        if($this->head==NULL)
        {
            echo "Empty Linked List";
        }
        else
        {
            $temp=$this->head;
            echo "Linked List :";
            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;

    }
    //Detecting loop of linked list
    public function detect_loop()
    {
      if($this->head==NULL)
      { 
        echo ("Empty Linked List\n");

        return;
      }

      $status=0;

      $first=$this->head;
      $second=$this->head;

      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
        $this->delete_loop($this->head);

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

  /*
  *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->head->next->next->next->next->next->next->next= $obj->head->next;
    
  $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.

New Comment







© 2021, kalkicode.com, All rights reserved