Home » Interview coding problems/challenges

Find length of loop in a linked list

In this article, we are going to learn how to detect loop in linked list and find its length using Floyd’s cycle detection algorithm? This problem has been featured in the coding round of Adobe, Qualcomm. Submitted by Radib Kar, on December 10, 2018

Problem statement

Given a linked list, write a program that checks whether the given Linked List contains a loop or not and if the loop is present then return the count of nodes in the loop or else return 0. (this is mainly a functional problem).

Example

Loop in the linked list

There is a loop in the above linked list.
As, 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 3 → 4 → 5 → 6 → 7 → 8 → 3...so on.

Thus, there is a loop between 3 and 8 and the length of loop is 6.

Solution Approach

The above problem has two sections:

1. Detecting loop in the linked list
2. Finding length of loop if loop exists

We declare two pointers: one slow pointer and another fast pointer. The slow pointer moves slowly, only one step at each iteration. The fast pointer moves fast, two steps at each iteration. Slow pointer and fast pointer are initially set to the head & head->next respectively.

If there is a loop then the fast pointer and slow pointer will point to a similar node after finite no of iteration
Else
The fast pointer will reach NULL.

Let’s solve the above example using this algorithm...

    Initially both points to head node...

    At iteration 0:
    slow points to 2 (head->next )
    fast points to 3  (head->next->next)
    
    At iteration 1:
    slow points to 3 (only one traverse one node)
    fast points to 5(traverse two nodes)
    
    At iteration 2: 
    slow points to 4 (only one traverse one node)
    fast points to 7  (traverse two nodes)
    
    At iteration 3: 
    slow points to 5 (only one traverse one node)
    fast points to 3 (traverse two nodes)
    
    At iteration 4: 
    slow points to 6 (only one traverse one node)
    fast points to 5  (traverse two nodes)
    
    At iteration 5: 
    slow points to 7 (only one traverse one node)
    fast points to 7 (traverse two nodes)

    both points to same node, loop detected

In case there’s no loop, let’s consider these case too...

Such an example is any single linked list terminated by NULL, 1 → 2 → 3 → 4 → 5 → 6 → NULL

In this case the fast pointer reaches the NULL fast and the program terminates detecting no loop.

Finding length of loop

    If there is no loop then length of loop is 0.
    Else
    Slow pointer is already pointing to the node at which we detected the loop.
    Now, set counter=1  & temp=slow->next;
    while (temp!=slow){
        temp=temp->next;
        counter++;
    } 
    Return counter; // length of loop

C++ Implementation to find length of loop in a linked list

#include <bits/stdc++.h>
using namespace std;

class Node{//linked list node
	public:
		int data;
		Node* next;
};

int loopLength(Node *head){
	Node* slow=head,*fast=head; //initialize
	while(slow && fast && fast->next){
		slow=slow->next; //slow pointer moves slowly
		fast=fast->next->next; //fast pointer moves fast
		if(fast==slow){//there is loop
			//count loop length
			Node* temp=slow;
			temp=temp->next;
			int count=1;
			while(temp!=slow){
				count++;
				temp=temp->next;
			}
			return count; //return loop length
		}
	}
	return 0;//if there is no loop
}


Node *newNode(int k){ //defining new node
	Node *temp = (Node*)malloc(sizeof(Node)); 
	temp->data = k; 
	temp->next = NULL; 
	return temp; 
} 

/* Driver program to test above function*/
int main() { 
	cout<<"linked list is built like the example\n";
	cout<<"1->2->3->4->5->6->7->8->3->4->....\n";
	Node *head = newNode(1); 
	head->next = newNode(2); 
	head->next->next = newNode(3); 
	head->next->next->next = newNode(4); 
	head->next->next->next->next = newNode(5);
	head->next->next->next->next->next = newNode(6);
	head->next->next->next->next->next->next = newNode(7);
	head->next->next->next->next->next->next->next = newNode(8);

	/* Create the loop  */
	//the next pinter of node having value 8 coonected to node having value 3
	head->next->next->next->next->next->next->next->next = head->next->next ; 

	printf("loop length: %d \n", loopLength(head)); 

	return 0; 
} 

Output

linked list is built like the example
1->2->3->4->5->6->7->8->3->4->....
loop length: 6