Find length of loop/cycle in given Linked List
Last Updated :
29 Oct, 2023
Given the head of a linked list. The task is to find if a loop exists in the linked list if yes then return the length of the loop in the linked list else return 0.
Examples:
Input: linked list = 
Output: 4
Explanation: The loop is present in the below-linked list and the length of the loop is 4.
Input: linked list = 4 -> 3 -> 7 -> 9 -> 2
Output: 0
Approach: Below is the idea to solve the problem:
Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point. It is also known that this common point is one of the loop nodes. Store the address of this common point in a pointer variable ptr. Then initialize a counter with 1 and start from the common point and keeps on visiting the next node and increasing the counter till the common pointer is reached again. At that point, the value of the counter will be equal to the length of the loop.
Follow the below steps to implement the idea:
- Find the common point in the loop by using the Floyd’s Cycle detection algorithm
- Store the pointer in a temporary variable and keep a count = 0
- Traverse the linked list until the same node is reached again and increase the count while moving to next node.
- Print the count as length of loop
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
int countNodes(struct Node* n)
{
int res = 1;
struct Node* temp = n;
while (temp->next != n) {
res++;
temp = temp->next;
}
return res;
}
int countNodesinLoop(struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
return countNodes(slow_p);
}
return 0;
}
struct Node* newNode(int key)
{
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}
int main()
{
struct 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 = head->next;
cout << countNodesinLoop(head) << endl;
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int countNodes(struct Node* n)
{
int res = 1;
struct Node* temp = n;
while (temp->next != n) {
res++;
temp = temp->next;
}
return res;
}
int countNodesinLoop(struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
return countNodes(slow_p);
}
return 0;
}
struct Node* newNode(int key)
{
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}
int main()
{
struct 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 = head->next;
printf("%d \n", countNodesinLoop(head));
return 0;
}
|
Java
import java.util.*;
import java.io.*;
public class GFG {
static class Node {
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
static int countNodes(Node n)
{
int res = 1;
Node temp = n;
while (temp.next != n) {
res++;
temp = temp.next;
}
return res;
}
static int countNodesinLoop(Node list)
{
Node slow_p = list, fast_p = list;
while (slow_p != null && fast_p != null
&& fast_p.next != null) {
slow_p = slow_p.next;
fast_p = fast_p.next.next;
if (slow_p == fast_p)
return countNodes(slow_p);
}
return 0;
}
static Node newNode(int key)
{
Node temp = new Node(key);
return temp;
}
public static void main(String[] args)
{
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 = head.next;
System.out.println(countNodesinLoop(head));
}
}
|
Python3
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def AddNode(self, val):
if self.head is None:
self.head = Node(val)
else:
curr = self.head
while(curr.next):
curr = curr.next
curr.next = Node(val)
def CreateLoop(self, n):
LoopNode = self.head
for _ in range(1, n):
LoopNode = LoopNode.next
end = self.head
while(end.next):
end = end.next
end.next = LoopNode
def detectLoop(self):
if self.head is None:
return 0
slow = self.head
fast = self.head
flag = 0
while(slow and slow.next and fast and
fast.next and fast.next.next):
if slow == fast and flag != 0:
count = 1
slow = slow.next
while(slow != fast):
slow = slow.next
count += 1
return count
slow = slow.next
fast = fast.next.next
flag = 1
return 0
myLL = LinkedList()
myLL.AddNode(1)
myLL.AddNode(2)
myLL.AddNode(3)
myLL.AddNode(4)
myLL.AddNode(5)
myLL.CreateLoop(2)
loopLength = myLL.detectLoop()
if myLL.head is None:
print("Linked list is empty")
else:
print(str(loopLength))
|
C#
using System;
class GFG {
class Node {
public int data;
public Node next;
public Node(int data)
{
this.data = data;
next = null;
}
}
static int countNodes(Node n)
{
int res = 1;
Node temp = n;
while (temp.next != n) {
res++;
temp = temp.next;
}
return res;
}
static int countNodesinLoop(Node list)
{
Node slow_p = list, fast_p = list;
while (slow_p != null && fast_p != null
&& fast_p.next != null) {
slow_p = slow_p.next;
fast_p = fast_p.next.next;
if (slow_p == fast_p)
return countNodes(slow_p);
}
return 0;
}
static Node newNode(int key)
{
Node temp = new Node(key);
return temp;
}
public static void Main(String[] args)
{
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 = head.next;
Console.WriteLine(countNodesinLoop(head));
}
}
|
Javascript
<script>
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function countNodes( n) {
var res = 1;
temp = n;
while (temp.next != n) {
res++;
temp = temp.next;
}
return res;
}
function countNodesinLoop( list) {
var slow_p = list, fast_p = list;
while (slow_p != null && fast_p != null && fast_p.next != null) {
slow_p = slow_p.next;
fast_p = fast_p.next.next;
if (slow_p == fast_p)
return countNodes(slow_p);
}
return 0;
}
function newNode(key) {
temp = new Node(key);
return temp;
}
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 = head.next;
document.write(countNodesinLoop(head));
</script>
|
Time complexity: O(N), Only one traversal of the linked list is needed.
Auxiliary Space: O(1), As no extra space is required.
Another Approach: Using Hash set (Unordered_set ) to keep the track of the visited nodes.
Algorithm steps:
- Initialize an empty hash set and a pointer
current to the head of the linked list.
- Traverse the linked list using
current:a. If the current node is already in the hash set, there is a loop:
- Initialize a variable
count to 1 and set a pointer startOfLoop to the current node.
- Increment
count and move current until it reaches startOfLoop again.
- Return
count, which represents the number of nodes in the loop.
b. If the current node is not in the hash set, mark it as visited by inserting it into the hash set and move current to the next node.
- If the traversal ends without finding a loop (i.e.,
current becomes nullptr), return 0 to indicate that there is no loop in the linked list.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
int countNodesinLoop(struct Node* list)
{
unordered_set<struct Node*> visited;
struct Node* current = list;
int count = 0;
while (current != nullptr) {
if (visited.find(current) != visited.end()) {
struct Node* startOfLoop = current;
do {
count++;
current = current->next;
} while (current != startOfLoop);
return count;
}
visited.insert(current);
current = current->next;
}
return 0;
}
struct Node* newNode(int key)
{
struct Node* temp = new struct Node;
temp->data = key;
temp->next = nullptr;
return temp;
}
int main()
{
struct 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 = head->next;
cout << countNodesinLoop(head) << endl;
return 0;
}
|
Java
import java.util.HashSet;
class Node {
int data;
Node next;
Node(int data)
{
this.data = data;
this.next = null;
}
}
public class Main {
static int countNodesInLoop(Node list)
{
HashSet<Node> visited = new HashSet<>();
Node current = list;
int count = 0;
while (current != null) {
if (visited.contains(current)) {
Node startOfLoop = current;
do {
count++;
current = current.next;
} while (current != startOfLoop);
return count;
}
visited.add(current);
current = current.next;
}
return 0;
}
public static void main(String[] args)
{
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = head.next;
System.out.println(countNodesInLoop(head));
}
}
|
Python3
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def countNodesInLoop(head):
visited = set()
current = head
count = 0
while current is not None:
if current in visited:
start_of_loop = current
while True:
count += 1
current = current.next
if current == start_of_loop:
break
return count
visited.add(current)
current = current.next
return 0
if __name__ == "__main__":
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = head.next
print(countNodesInLoop(head))
|
C#
using System;
using System.Collections.Generic;
namespace Geek
{
class Node
{
public int data;
public Node next;
}
class GFG
{
static int CountNodesInLoop(Node list)
{
HashSet<Node> visited = new HashSet<Node>();
Node current = list;
int count = 0;
while (current != null)
{
if (visited.Contains(current))
{
Node startOfLoop = current;
do
{
count++;
current = current.next;
} while (current != startOfLoop);
return count;
}
visited.Add(current);
current = current.next;
}
return 0;
}
static Node NewNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
static void Main(string[] args)
{
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 = head.next;
Console.WriteLine(CountNodesInLoop(head));
Console.ReadLine();
}
}
}
|
Javascript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function countNodesInLoop(list) {
const visited = new Set();
let current = list;
let count = 0;
while (current !== null) {
if (visited.has(current)) {
const startOfLoop = current;
do {
count++;
current = current.next;
} while (current !== startOfLoop);
return count;
}
visited.add(current);
current = current.next;
}
return 0;
}
function newNode(key) {
const temp = new Node(key);
return temp;
}
function main() {
const 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 = head.next;
console.log(countNodesInLoop(head));
}
main();
|
Output:
4
Time complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(N).
Related Articles:
This article is contributed by Shubham Gupta.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...