Length of the loop in the 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.
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.
Source:emre.me
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.
Frequently asked questions
- How do you find the length of a linked list?
Answer: 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.
2. Is it possible to find a loop in a linked list?
Answer: Yes, we can find a loop in a linked list using Floyd's cycle detection algorithm.
3. How would you find from which node the loop starts?
Answer: This is another variation of the above problem. Read the complete solution here.
4. How do I find a loop in a list?
Answer: 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.
Key Takeaways
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.
If you're looking to prepare for interviews at top product-based companies, CodeStudio is the place to go. It's a fantastic platform created by a group of ambitious enthusiasts and working professionals with backgrounds in Google, Amazon, and Microsoft.
To know more about interview problems and experience, do visit CodeStudio.
Happy learning!
Comments
No comments yet
Be the first to share what you think