1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Implementation
4.
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

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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

## Solution Approach

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

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.

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()

{

// loop part

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

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