.jpg)
Detect Loop in a Linked List
Problem
Given the head of a Singly Linked List, determine whether the list contains a loop (cycle).
A loop occurs when a node’s next pointer points to a previous node instead of NULL.
Return:
- true if a loop exists
- false otherwise
Example
Looped List
1 → 2 → 3 → 4 → 5
↑ ↓
← ← ← ←
Output
True
Non-Looped List
1 → 2 → 3 → 4 → NULL
Output
False
Approach 1 — Floyd’s Cycle Detection (Tortoise and Hare)
Idea
Use two pointers moving at different speeds:
- Slow pointer moves one step
- Fast pointer moves two steps
If a loop exists, they will eventually meet inside the loop.
If fast reaches NULL → no loop.
Steps
- Initialize:
- slow = head
- fast = head
- Traverse while fast and fast.next exist
- Move:
- slow = slow.next
- fast = fast.next.next
- If slow == fast → loop detected
- If fast reaches NULL → no loop
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 detectLoop(struct Node* head) {
struct Node* slow = head;
struct Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return 1;
}
return 0;
}
int main() {
struct Node *head, *n2, *n3, *n4;
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));
head->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n2; // loop
printf("%d", detectLoop(head));
return 0;
}Output
1
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;
}
};
bool detectLoop(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
int main() {
Node* head = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3);
Node* n4 = new Node(4);
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n2; // loop
cout << detectLoop(head);
return 0;
}Output
1
Java Implementation
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static boolean detectLoop(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}
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);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n2; // loop
System.out.println(detectLoop(head));
}
}
Output
true
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def detect_loop(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
head = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
head.next = n2
n2.next = n3
n3.next = n4
n4.next = n2 # loop
print(detect_loop(head))
Output
True
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function detectLoop(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast)
return true;
}
return false;
}
let head = new Node(1);
let n2 = new Node(2);
let n3 = new Node(3);
let n4 = new Node(4);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n2; // loop
console.log(detectLoop(head));
Output
true
Approach 2 — Using Hash Set (Visited Nodes)
Idea
In this approach, we keep track of all visited nodes using a Hash Set (or any data structure that supports fast lookup).
While traversing the list:
- If we encounter a node that is already in the set → a loop exists
- If we reach NULL → no loop
This works because in a looped list, nodes repeat.
Steps
- Create an empty Hash Set
- Traverse the linked list
- For each node:
- If node exists in set → return true
- Else insert node into set
- If traversal ends → return false
Time Complexity
O(N)
Space Complexity
O(N)
(for storing visited nodes)
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 detectLoop(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)
return 1;
}
visited[count++] = temp;
temp = temp->next;
}
return 0;
}
int main() {
struct Node *head, *n2, *n3, *n4;
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));
head->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n2; // loop
printf("%d", detectLoop(head));
return 0;
}Output
1
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;
}
};
bool detectLoop(Node* head) {
unordered_set visited; // store node addresses
Node* temp = head;
while (temp != NULL) {
if (visited.find(temp) != visited.end())
return true;
visited.insert(temp);
temp = temp->next;
}
return false;
}
int main() {
Node* head = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3);
Node* n4 = new Node(4);
head->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n2; // loop created
cout << detectLoop(head); // prints 1 if loop exists, else 0
return 0;
}Output
1
Java Implementation
import java.util.HashSet;
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static boolean detectLoop(Node head) {
HashSet visited = new HashSet<>();
Node temp = head;
while (temp != null) {
if (visited.contains(temp))
return true;
visited.add(temp);
temp = temp.next;
}
return false;
}
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);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n2; // loop
System.out.println(detectLoop(head));
}
}
Output
true
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def detect_loop(head):
visited = set()
temp = head
while temp:
if temp in visited:
return True
visited.add(temp)
temp = temp.next
return False
head = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
head.next = n2
n2.next = n3
n3.next = n4
n4.next = n2 # loop
print(detect_loop(head))
Output
True
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function detectLoop(head) {
let visited = new Set();
let temp = head;
while (temp !== null) {
if (visited.has(temp))
return true;
visited.add(temp);
temp = temp.next;
}
return false;
}
let head = new Node(1);
let n2 = new Node(2);
let n3 = new Node(3);
let n4 = new Node(4);
head.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n2; // loop
console.log(detectLoop(head));
Output
true
.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)
