# 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.

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
//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;
}
}
}
//return length of loop
int counter=1;
temp=temp->next;
counter++;
}
return counter;
}

}
int status=0;
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

//set loop

}``````

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

public:
void insert(int);
void detect_loop();
int loop_length(Node*);
};
}
//insert Node element
//Create dynamic node
Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow"<<endl;
}else{
node->data=value;
node->next=NULL;
}else{
//find last node
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=node;
}
}
}
//return length of loop
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
}
int status=0;
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(){
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.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;
}
}

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

}
public void detectLoop() {
} else {
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;
}
}
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) {
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.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

def __init__(self):
#Assign default value

#insert new node to linked list
def insert(self,data):
node=Node(data)
node.next=None
else:
while temp.next!=None:
temp=temp.next
temp.next=node
#return loop length
def loopLength(self,other):
couter=1
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):
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():
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.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 Program(){
}
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
newNode.next=null;
else{
//get middle node
while(temp.next!=null ){
temp=temp.next;

}

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(){
}else{
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;
}
}
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.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;
}
}

function __construct()
{
}
/*
* Append the Given data value at end of linked list
* Fun : insert
* Parm: data value
*@return None
*/
function insert(\$data)
{
\$newNode=new Node(\$data);
{
}else{
//find last node of linked list
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
\$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()
{
{
}
\$status=0;

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()
{
{
}
else
{
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

/*
*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->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.