Find length of loop in linked list

Linked list is element of nodes, Suppose given linked list are contain loops. That means last node of linked list is not NULL. And our goal is to detect loop length how many number of nodes are involved. That is interesting and commonly asked question in linked list programming. In this post we are discussing about how to solve this problem in effective manner.

First see the situation of loop in linked list. Suppose we are inserted the following (1,2,3,4,5,6,7,8) node in a sequence. And last node of this linked list are store the reference of other node of linked list.

Length of Loop in linked list

In this example last node is connected to 3rd node of linked list. And this is create a loop when we iterates this linked list. We can solve this problem in following way.

Process: 1) First our goal is detect loop in linked list. So we are need to iterate linked list nodes element. We are use two pointer variables first and second.

Here given code implementation process. And assign the address of head node to both pointers.

2) 2) In this case second pointer variable are visited every second upcoming nodes. that means this variable logical increment by two. and as respect to first pointer are visiting next node.

3) Repeat step 2 process until there are first and second pointer are not hold same node address. So finally we get nodes which part of loop nodes. Then do step 4.

4) Step 3 we are get node which is part of loops. Finally iterating linked list by using of this get node. This iteration is similar to circular linked list.

//C Program to find length of linke list loop
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
int loop_length(struct Node*);
void detect_loop(struct Node*);
//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 position
      temp->next=node;
    }
  }
}
//return length of loop
int loop_length(struct Node*head){
  struct Node*temp=head;
  int counter=1;
  while(temp->next!=head){
    temp=temp->next;
    counter++;
  }
  return counter;
}

void detect_loop(struct Node*head){
  if(head==NULL){
    printf("\n Empty Linked List");
  }
  int status=0;
  struct Node*first=head,*second=head;
  while(second!=NULL && second->next!=
    NULL && second->next->next != NULL){
    second=second->next->next; //increment by 2 node visit
    first=first->next; //visit to next node
    if(first==second){
      //found loop
      status=1;
      break;
    }
  }
  if(status==1){
    printf("Length of loop in linked list : %d\n",loop_length(first));
  }else{
    printf("\n No loop in this linke List");
  }
  
}
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);
  insert(&head,8);
  //set loop
  head->next->next->next->next->next->next->next->next=head->next->next;
  detect_loop(head);
  
}

Output

Size of loop in linked list : 6
//C++ Program to find length of linked list loop

#include<iostream>
using namespace std;

//create structure
struct Node{
  int data;
  struct Node*next;
};
class LinkedList{
  
public:
  Node*head;
  LinkedList();
  void insert(int);
  void detect_loop();
  int loop_length(Node*);
};
//set head pointer value
LinkedList ::LinkedList(){
  head=NULL;
}
//insert Node element
void LinkedList:: insert(int value){
    //Create dynamic node
  Node*node=new Node;
  if(node==NULL){
    cout<<"Memory overflow"<<endl;
  }else{
    node->data=value;
    node->next=NULL;
    if(head==NULL){
      head=node;
    }else{
      Node*temp=head;
      //find last node
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//return length of loop
int LinkedList:: loop_length(struct Node*init){
  struct Node*temp=init;
  int counter=1;
  while(temp->next!=init){
    temp=temp->next;
    counter++;
  }
  return counter;
}
//check loop is exist in this linked list
void LinkedList:: detect_loop(){
  if(head==NULL){
    cout<<"\n Empty Linked List";
  }
  int status=0;
  Node*first=head,*second=head;
  while(second!=NULL && second->next!=
    NULL && second->next->next != NULL){
    second=second->next->next; //increment by 2 node visit
    first=first->next; //visit to next node
    if(first==second){
      //found loop
      status=1;
      break;
    }
  }
  if(status==1){
    cout<<"Length of loop in linked list :"<<loop_length(first)<<endl;
  }else{
    cout<<"\n No loop in this linke List"<<endl;
  }
}

int main(){
  LinkedList obj=LinkedList();
  //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);
  obj.insert(8);
  obj.head->next->next->next->next->next->next->next->next= obj.head->next->next;
  obj.detect_loop();
  return 0;
}

Output

Length of loop in linked list :6
//java Program to 
//find length of loop in linked list 
class Node {
  public int data;
  public Node next;
  public Node(int value) {
    data = value;
    next = null;
  }
}

public class LinkedList {

  public Node head;
  //Class constructors
  LinkedList() {
    head = null;
  }
  //insert node at last of linke list
  public void insert(int value) {
    //Create a node
    Node node = new Node(value);
    if (head == null) head = node;
    else {
      Node temp = head;
      //find lase node
      while (temp.next != null) {
        temp = temp.next;
      }
      //add node
      temp.next = node;
    }

  }
  //Detecting loop of linked list
  public void detectLoop() {
    if (head == null) {
      System.out.println("Empty Linked List ");
    } else {
      int status = 0;
      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;
        }
      }
      if (status == 1) {
        status = lengthLoop(first);
        System.out.println("Length of Loop :" + status);

      } else {
        System.out.println("No loop in this linked list");
      }

    }
  }
  //find the size of linke list
  public int lengthLoop(Node init) {
    int counter = 1;
    Node temp = init;
    while (temp.next != init) {
      temp = temp.next;
      counter++;
    }
    return counter;

  }

  public static void main(String[] args) {
    LinkedList obj = new LinkedList();
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);

    obj.head.next.next.next.next.next.next.next.next = obj.head.next.next;

    obj.detectLoop();

  }
}

Output

Length of Loop :6
#Python program to find length of loop
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

#create class Linked    
class Linked:
    def __init__(self):
        #Assign default value
        self.head=None
    
    #insert new node to linked list  
    def insert(self,data):
        node=Node(data)
        node.next=None
        if self.head==None:
            self.head=node
        else:
            temp=self.head
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node
    #return loop length        
    def loopLength(self,other):
        couter=1
        temp=self.head
        while temp.next!=other:
            #visit next node
            temp=temp.next
            #modified counter value
            couter+=1

        return couter       
    #find loop is exist or not    
    def detectLoop(self):
        first=self.head
        second=self.head
        status=0
        while second!=None and second.next!=None and second.next.next!=None:
            first=first.next
            second=second.next.next
            if(first==second):
                status=1
                break
        if(status==1):
            status=self.loopLength(first)
            print("Length of loop : {}".format(status))
        else:
            print("No loop in this linked list")    
def main():
    #Create Object of class Linked
    obj=Linked()
    #Insert Linked Elements
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    #set loop
    obj.head.next.next.next.next.next.next.next.next = obj.head.next.next;

    obj.detectLoop();
    

if __name__=="__main__":
    main()

Output

Length of loop : 6
//C# program to find the length of linked list loop
using System;
//node class
public class Node{
  public  int data;
  public  Node next;
}
class Program
{
  public Node head;
  public Program(){
    head=null;
  }
  //insert node of linked list
  public void insert(int data){
    Node newNode=new Node();
    newNode.data=data;
    newNode.next=null;
    if(head==null) head=newNode;
    else{
      Node temp=head;
            //get middle node
      while(temp.next!=null ){
        temp=temp.next;

      }
           //add new node

      temp.next=newNode;
    }
  }

  //return length of linked list loop
  public int lengthLoop(Node init){
    int counter=1;
    Node temp=init;
    while(temp.next!=init){
      temp=temp.next;
      counter++;
    }
    return counter;
    
  }
  //check loop is exist or not
  public void detectLoop(){
    if(head==null){
      Console.Write("Empty Linked List ");
    }else{
      int status=0;
      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;
        }
      }
      if(status==1){
        status=lengthLoop(first);
        Console.Write("Length of Loop : {0}",status);

      }else{
        Console.Write("No loop in this linked list");
      }
      
    }
  }

  static void Main(){

    Program obj=new Program();
    //insert element value
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    //set loop
    obj.head.next.next.next.next.next.next.next.next = obj.head.next.next;

    obj.detectLoop();
  }
}

Output

Length of Loop : 6
<?php
//Php program 
// Find length of linked list loop
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
    */
    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;
        }
    }
    //return length of loop
    function loop_length($init){
      
      $temp=$init;
      $counter=1;
      
      while($temp->next!=$init){
        $temp=$temp->next;
        $counter++;
      }
      return $counter;
    }
    //check loop is exist in this linked list
    function detect_loop()
    {
      if($this->head==NULL)
      {
        echo"<br> Empty Linked List";
      }
      $status=0;
      $first=$this->head;
      $second=$this->head;
      
      while($second!=NULL && $second->next!=
        NULL && $second->next->next != NULL)
      {
        
        $second=$second->next->next; //increment by 2 node visit
       
        $first=$first->next; //visit to next node
        
        if($first==$second)
        {
          //found loop
          $status=1;
          break;
        }
      }
      if($status==1)
      {
        
        echo"Length of loop in linked list :".$this->loop_length($first)."<br>";
      
      }
      else
      {
        echo"<br> No loop in this linke List <br>";
      }
    }
    //Display all inserted node in linked list
    function display()
    {
        if($this->head==NULL)
        {
            echo "Empty Linked List";
        }
        else
        {
            $temp=$this->head;
            echo "<br>Linked List :";
            while($temp!=NULL)
            {
                //display node value
                echo "&nbsp;&nbsp;".$temp->data;
                $temp=$temp->next; //visit to next node
            }
        }   
    }
}
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);
  $obj->insert(8);
  $obj->head->next->next->next->next->next->next->next->next= $obj->head->next->next;
  $obj->detect_loop();
}
main();
?>

Output

Length of loop in linked list :6


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