Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Implementation
4.
Frequently Asked Questions
4.1.
How do you find the length of a linked list? 
4.2.
Is it possible to find a loop in a linked list? 
4.3.
How would you find from which node the loop starts? 
4.4.
How do I find a loop in a list? 
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Length of the Loop in the Linked List

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Linked List

Introduction

The linked list data structure is one of the most important topics in technical interviews. It forms a variety of tricky yet straightforward questions. This article explains one such question in detail.

 

Finding whether a linked list contains a loop is one of the classic problems of a linked list. A slight variation of this question is to find the length of the loop in the linked list.
 

So, let’s get started!

Problem Statement

Given a singly linked list, we've to find the length of the loop in the linked list if a loop is present. If there is no loop, return 0.

 

For example, a loop can be found in the linked list below, and its length is 6. 

Illustration Image



Solution Approach

This solution to this problem can be broken down into two parts to reduce its complexity.

 

Part-1: Detect if linked list has a loop

Part-2: Finding the length of the loop.

 

Part-1:

Floyd’s cycle detection algorithm is used to check whether the linked list contains a cycle or not. It uses a two-runner approach to do so. Let’s first understand this algorithm in brief.
 

The fast runner and slow runner approach is an easy way to detect if a linked list has a loop. A fast runner moves two steps at a time, while a slow runner moves one step. If there is a loop, they must collide at some point. This is how Floyd's cycle detection algorithm works.

To learn about this algorithm in detail, we suggest you read this fantastic blog, Floyd’s cycle detection algorithm.

We’ll be using this algorithm to solve the first part of this problem. 

 

Part-2:

The point at which the fast runner and the slow runner will meet, let's call it the point of collision. In a pointer variable, we'll store the collision point's address. Then, starting from the collision point, increment the counter as we visit each node until we reach the collision point again.

 

At this time, the counter's value will be equal to the length of the loop in the linked list. Now, simply return the counter value.

 

Let’s see the implementation of this approach.

Implementation

The implementation of the above approach to find the length of the loop in the linked list is given below:

//Program to find the length of the loop in the linked list

#include<bits/stdc++.h>

using namespace std;



struct Node

{

	int data;

	struct Node* next;

};



// Function to find the length of the loop in the linked list.

int lengthOfLoop(struct Node *n)

{

	int ans =  1;

	struct Node *temp =  n;

	while (temp->next != n)

	{

		ans++;

		temp = temp->next;

	}

	return ans;

}



//Function to detect loop

int isLoopPresent(struct Node *list)

{

	int temp = 0;

	struct Node *S_runner =  list; // slow runner

	    struct Node *F_runner =  list; // fast runner



	while (S_runner !=  NULL && F_runner !=  NULL && F_runner->next !=  NULL)

	{

		S_runner = S_runner->next;

		F_runner = F_runner->next->next;



// Point of collision

		if (S_runner == F_runner)

			return lengthOfLoop(S_runner);

	}



	   // if no loop is present

	return temp;

}



struct Node *newNode(int key)

{

	struct Node *ptr = (struct Node*)malloc(sizeof(struct Node));

	ptr->data = key;

	ptr->next =  NULL;

	return ptr;

}

// Driver Code

int main()

{

	struct Node *head =  newNode(17);

	head->next = newNode(21);

	head->next->next = newNode(33);

	head->next->next->next = newNode(49);

	head->next->next->next->next = newNode(18);

	head->next->next->next->next->next = newNode(57);

	head->next->next->next->next->next->next = newNode(28);



// loop part

	head->next->next->next->next->next->next->next = head->next;



	int length = isLoopPresent(head);

	if (length >  0)

		       cout << "The length of loop in the linked list is: " << length << endl;

	   else

		       cout << "Loop is not present in the linked list" << endl;



	return 0;

}

 

 

Output:

The length of the loop in the linked list is: 6

 

Now, let’s move towards frequently asked questions on this topic.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How do you find the length of a linked list? 

To find the length of the linked list, we’ve to keep a counter and iterate through the linked list until the node starts pointing to null. Keep increasing the pointer at every node. The value of that pointer will be equal to the length of the linked list. 

Is it possible to find a loop in a linked list? 

Yes, we can find a loop in a linked list using Floyd's cycle detection algorithm.

How would you find from which node the loop starts? 

This is another variation of the above problem.

How do I find a loop in a list? 

An easy way to detect if a linked list has a loop is through the fast runner and slow runner approach. A fast runner moves two steps at a time, while a slow runner moves one step. If there is a loop, they must collide at some point.

Conclusion

Finding the length of the loop in the linked list is one of the most straightforward problems asked in various exams. 

Looking for a one-stop destination for the linked list concepts, read this amazing article.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To study more about Linked Lists, refer to Applications Of Linked Lists.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Detect a Loop in a Linked List
Next article
Rotate a Linked List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass