How to detect a loop in a Linked list
In a linked list, last node of the list is obtained by searching for a null value in the address part of a node. However, if we do not find any node containing the null value, it indicates the presence of cycle/loop in the linked list. There are two possibilities for the presence of loop/cycle. Cycle may be from the last node or it can be from some intermediate node in the list as shown in the diagram.
There are three ways to detect a loop in a linked list. They are as listed below.
- Traversing through the list
- Using HashSet
- Using Floyd's Cycle Detection Algorithm
Method-1: Traversing through the list
This is the traditional approach to detect a loop in a linked list. Here, we will traverse a list using two nested loops. Here, we are taking two pointers p and q. The pointer p will traverse from the first node to last node exactly once. However, the pointer q will every time start with first node and traverse till pointer p. Every time during looping q will check for whether it was pointing to the same node as p. If so, it means there is cycle.
// Program to detect a loop in a linked list
import java.util.HashSet;
// Node class
class Node {
// class variables
int data;
Node next;
// Constructor
Node(int x) {
data = x;
next = null;
}
}
// Main class
public class Main {
public static void main(String args[]) {
Node head = new Node(10);
Node n1 = new Node(20);
head.next = n1;
Node n2 = new Node(30);
n1.next = n2;
Node n3 = new Node(40);
n2.next = n3;
Node n4 = new Node(50);
n3.next = n4;
// Creating loop
n2.next = head;
Main o = new Main();
o.findcycle(head);
}
// Function to detect a loop
public void findcycle(Node head) {
// Initializing
Node p = head;
int count = 0;
// Traversing the Linked List.
while (p != null) {
// Initializing
Node q = head;
p = p.next;
count++;
// Iterating q from first node till current node
while (count > 0) {
System.out.println("Comparing node " + p.data + " with " + q.data);
if (q == p) {
System.out.println("Cycle found");
return;
}
q = q.next;
count--;
}
}
}
}Output:
Comparing node 20 with 10
Comparing node 30 with 10
Comparing node 10 with 10
Cycle found
Method-2: Using HashSet
This is the simplest approach to detect a loop in a linked list. Firstly, we will create an empty hashset. Thereafter, we will traverse the nodes in the list one by one and store these node addresses in a hash table. Now, before inserting a node, we will check if the node is already present using the contains method of HashSet. If the current node is already present in the hash table, then it indicates that there is a loop in the linked list. However, if we reach to the end of the list and none of the nodes are repeated means that there is no loop in the linked list.
// Program to detect a loop in a linked list
import java.util.HashSet;
// Node class
class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
// Main class
public class Main {
public static void main(String args[]) {
Node head = new Node(10);
Node n1 = new Node(20);
head.next = n1;
Node n2 = new Node(30);
n1.next = n2;
Node n3 = new Node(40);
n2.next = n3;
Node n4 = new Node(50);
n3.next = n4;
// Creating loop
n2.next = head;
// Object creation and function calling
Main o = new Main();
o.findcycle(head);
}
// Function to detect a cycle
public void findcycle(Node head) {
Node p = head;
HashSet h = new HashSet < > ();
// Traverse the Linked List.
while (p != null) {
System.out.println("Inserting node " + p.data);
// Checking if current node is already present
if (h.contains(p)) {
System.out.println("Cycle found");
return;
}
// Adding the current node as it was not previously added
h.add(p);
p = p.next;
}
System.out.println("Cycle not found");
}
}Output:
Inserting node 10
Inserting node 20
Inserting node 30
Inserting node 10
Cycle found
Method-3: Using Floyd's Cycle Detection Algorithm
This is the fastest approach to detect a loop in a linked list. Here, we will maintain two pointer slow pointer(s) and fast pointer(f) that moves in the list one step and two step at a time respectively. If there is a loop in the linked list, both the pointers will meet at some node. However, if there is no loop then fast pointer will reach to the end of the list.
// Program to detect a loop in a linked list
import java.util.HashSet;
// Node class
class Node {
// Class variables
int data;
Node next;
// Constructor
Node(int x) {
data = x;
next = null;
}
}
// Main class
public class Main {
public static void main(String args[]) {
Node head = new Node(10);
Node n1 = new Node(20);
head.next = n1;
Node n2 = new Node(30);
n1.next = n2;
Node n3 = new Node(40);
n2.next = n3;
Node n4 = new Node(50);
n3.next = n4;
// Creating loop
n2.next = head;
// Object creation and function calling
Main o = new Main();
o.findcycle(head);
}
// Function to detect cycle
void findcycle(Node head) {
Node s = head, f = head;
int found = 0;
while (s != null && f != null && f.next != null) {
// s pointer moves 1 step everytime whereas f pointer moves two step at a time
s = s.next;
f = f.next.next;
System.out.println("Slow pointer is at " + s.data);
System.out.println("Fast pointer is at " + f.data);
// if both the pointers point to the same node then there is a loop
if (s == f) {
found = 1;
break;
}
}
if (found == 1)
System.out.println("Cycle found");
else
System.out.println("No cycle found");
}
}Output:
Slow pointer is at 20
Fast pointer is at 30
Slow pointer is at 30
Fast pointer is at 20
Slow pointer is at 10
Fast pointer is at 10
Cycle found
Summary
The knowledge of detecting loop in a linked list is very useful concept from the view point of data structure. In many situations, we will need to detect a loop in a linked list when multiple threads are inserting the data in the single list. So, we can use any of the approach discussed here. In this tutorial, we covered three different approaches to detect a loop in a linked list. As per the complexity and size of data in an application, we can choose an appropriate approach to detect a loop in a linked list.
We learned in detail about this with source code. All in all, this tutorial, covers everything that you need to know in order to have a clear view on detecting a loop in a Linked list.
References
