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:**

The above problem has two sections:

- Detecting loop in the linked list
- 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL