
📖 Introduction
A linked list is a widely used data structure in computer science. It is made up of nodes, where each node contains some data and a pointer (or reference) to the next node. Ideally, a linked list should end with null. However, sometimes due to programming mistakes or faulty pointer assignments, a cycle (or loop) may form.
A cycle in a linked list occurs when a node’s next pointer refers back to a previous node instead of pointing to null. This creates an endless loop, causing issues such as:
Infinite traversal while iterating through the list.
Memory leaks and performance problems.
Incorrect results in algorithms that depend on sequential traversal.
Detecting and removing cycles is a must-know skill in data structures and algorithms, especially for interviews and real-world programming.
🔎 What is a cycle in a linked list?
A cycle means the linked list does not terminate at null. Instead, the last node links back to one of the earlier nodes, creating a loop.
Example 1:
Input: 1 -> 3 -> 4 -> 3 (back to node 3)
Output: true
Here, node 4 connects back to node 3, forming a cycle.
Example 2:
Input: 1 -> 8 -> 3 -> 4 -> NULL
Output: false
In this case, the last node points to null, so no cycle exists.
🛠️ Approaches to detect a cycle
There are two popular ways to detect a cycle in a linked list:
✅ 1. Hashing Approach (Naive Method)
We use a HashSet to keep track of visited nodes.
Traverse the list node by node.
If a node is already present in the HashSet, it means the list has a cycle.
If traversal reaches
null, there is no cycle.
Time Complexity: O(n)
Space Complexity: O(n)
Java Example using HashSet:
import java.util.HashSet;
class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
class DetectCycleHashing {
static boolean detectLoop(Node head) {
HashSet<Node> visited = new HashSet<>();
while (head != null) {
if (visited.contains(head)) {
return true; // Cycle found
}
visited.add(head);
head = head.next;
}
return false; // No cycle
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(3);
head.next.next = new Node(4);
head.next.next.next = head.next; // Creates a cycle
System.out.println(detectLoop(head)); // Output: true
}
}

Join the conversation! Your thoughts help the community grow.