.jpg)
Length of Loop in Linked List
Problem
Given the head of a Singly Linked List, determine the length of the loop (cycle) if a loop exists.
If no loop exists, return 0.
Example
Looped List
1 → 2 → 3 → 4 → 5
↑ ↓
← ← ← ←
Loop Length
3
(Loop contains nodes 3 → 4 → 5)
Approach 1 — Floyd’s Cycle Detection + Counting
Idea
- First detect the loop using slow and fast pointers
- When they meet, a loop exists
- From meeting point, traverse the loop until coming back to same node
- Count the nodes visited
Steps
- Initialize slow and fast at head
- Move:
- slow → one step
- fast → two steps
- If they meet → loop found
- Start counting from meeting point
- Move until returning to same node
- Return count
Time Complexity
O(N)
Space Complexity
O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
int countLoop(struct Node* head) {
struct Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
int count = 1;
struct Node* temp = slow->next;
while (temp != slow) {
count++;
temp = temp->next;
}
return count;
}
}
return 0;
}
int main() {
struct Node *head, *n2, *n3, *n4, *n5;
head = (struct Node*)malloc(sizeof(struct Node));
n2 = (struct Node*)malloc(sizeof(struct Node));
n3 = (struct Node*)malloc(sizeof(struct Node));
n4 = (struct Node*)malloc(sizeof(struct Node));
n5 = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n3; // loop starts at 3
printf("%d", countLoop(head));
return 0;
}Output
3
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
int countLoop(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
int count = 1;
Node* temp = slow->next;
while (temp != slow) {
count++;
temp = temp->next;
}
return count;
}
}
return 0;
}
int main() {
Node* head = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3);
Node* n4 = new Node(4);
Node* n5 = new Node(5);
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n3;
cout << countLoop(head);
return 0;
}Output
3
Java Implementation
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static int countLoop(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
int count = 1;
Node temp = slow.next;
while (temp != slow) {
count++;
temp = temp.next;
}
return count;
}
}
return 0;
}
public static void main(String[] args) {
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n3;
System.out.println(countLoop(head));
}
}
Output
3
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def count_loop(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
count = 1
temp = slow.next
while temp != slow:
count += 1
temp = temp.next
return count
return 0
head = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
head.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n3
print(count_loop(head))
Output
3
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function countLoop(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let count = 1;
let temp = slow.next;
while (temp !== slow) {
count++;
temp = temp.next;
}
return count;
}
}
return 0;
}
let head = new Node(1);
let n2 = new Node(2);
let n3 = new Node(3);
let n4 = new Node(4);
let n5 = new Node(5);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n3;
console.log(countLoop(head));
Output
3
Approach 2 — Using Hash Set (Visited Nodes)
Idea
In this approach, we detect the loop and compute its length using a Hash Set.
While traversing:
- Store each visited node in the set
- If a node repeats → loop detected
- Start counting nodes from that repeated node until we reach it again
Steps
- Create an empty Hash Set
- Traverse the list
- If node already exists in set → loop start found
- From that node, traverse until reaching same node again
- Count nodes in the loop
- Return count
- If traversal reaches NULL → return 0
Time Complexity
O(N)
Space Complexity
O(N)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
#define MAX 1000
struct Node {
int data;
struct Node* next;
};
int countLoop(struct Node* head) {
struct Node* visited[MAX];
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
for (int i = 0; i < count; i++) {
if (visited[i] == temp) {
int loopLen = 1;
struct Node* start = temp->next;
while (start != temp) {
loopLen++;
start = start->next;
}
return loopLen;
}
}
visited[count++] = temp;
temp = temp->next;
}
return 0;
}
int main() {
struct Node *head, *n2, *n3, *n4, *n5;
head = (struct Node*)malloc(sizeof(struct Node));
n2 = (struct Node*)malloc(sizeof(struct Node));
n3 = (struct Node*)malloc(sizeof(struct Node));
n4 = (struct Node*)malloc(sizeof(struct Node));
n5 = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n3;
printf("%d", countLoop(head));
return 0;
}
Output
3
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
#include "unordered_set"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
int countLoop(Node* head) {
unordered_set visited; // FIXED
Node* temp = head;
while (temp != NULL) {
if (visited.count(temp)) {
int count = 1;
Node* start = temp->next;
while (start != temp) {
count++;
start = start->next;
}
return count;
}
visited.insert(temp);
temp = temp->next;
}
return 0;
}
int main() {
Node* head = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3);
Node* n4 = new Node(4);
Node* n5 = new Node(5);
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n3; // loop starts at node 3
cout << countLoop(head);
return 0;
}Output
3
Java Implementation
import java.util.HashSet;
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static int countLoop(Node head) {
HashSet visited = new HashSet<>();
Node temp = head;
while (temp != null) {
if (visited.contains(temp)) {
int count = 1;
Node start = temp.next;
while (start != temp) {
count++;
start = start.next;
}
return count;
}
visited.add(temp);
temp = temp.next;
}
return 0;
}
public static void main(String[] args) {
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n3;
System.out.println(countLoop(head));
}
}
Output
3
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def count_loop(head):
visited = set()
temp = head
while temp:
if temp in visited:
count = 1
start = temp.next
while start != temp:
count += 1
start = start.next
return count
visited.add(temp)
temp = temp.next
return 0
head = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
head.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n3
print(count_loop(head))
Output
3
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function countLoop(head) {
let visited = new Set();
let temp = head;
while (temp !== null) {
if (visited.has(temp)) {
let count = 1;
let start = temp.next;
while (start !== temp) {
count++;
start = start.next;
}
return count;
}
visited.add(temp);
temp = temp.next;
}
return 0;
}
let head = new Node(1);
let n2 = new Node(2);
let n3 = new Node(3);
let n4 = new Node(4);
let n5 = new Node(5);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n3;
console.log(countLoop(head));
Output
3
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
