# 3 different ways to detect a loop in a Linked List

Written By - Sweety Rupani

## 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 n1 = new Node(20);
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
Main o = new Main();
}

// Function to detect a loop
// Initializing
int count = 0;

while (p != null) {
// Initializing

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 n1 = new Node(20);
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

// Object creation and function calling
Main o = new Main();
}

// Function to detect a cycle
HashSet h = new HashSet < > ();

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;
}
p = p.next;
}
}
}``````

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 n1 = new Node(20);
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

// Object creation and function calling
Main o = new Main();
}

// Function to detect cycle
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

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation. For any other feedbacks or questions you can either use the comments section or contact me form.