Java Program to Detect loop in the LinkedList
What is LinkedList in Java ?
A linked list is a linear data structure in which each element (called a node) stores a reference to the next element in the list. Linked lists are dynamic data structures, which means that their size can change during the execution of a program. In contrast, arrays have a fixed size, which means that you need to specify the size of the array when you create it and you cannot change it later.
Ways to detect a loop in a linkedList in Java:
- Floyd’s Cycle-Finding Algorithm (also known as the Tortoise and Hare Algorithm): This algorithm uses two pointers, one moving at a slower pace (the tortoise) and the other moving at a faster pace (the hare). If there is a loop in the linked list, the hare will eventually catch up to the tortoise and they will both be pointing to the same node, indicating that there is a loop in the linked list.
Here’s the Pseudo code in Java for this algorithm:
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
- HashSet: This algorithm uses a HashSet to store the nodes as they are traversed. If a node has already been added to the HashSet, it means that there is a loop in the linked list.
Here’s the code Pseudo in Java for this algorithm:
public static boolean hasCycle(ListNode head) {
Set nodes = new HashSet<>();
while (head != null) {
if (nodes.contains(head)) {
return true;
}
nodes.add(head);
head = head.next;
}
return false;
}
Example of the Floyd’s Cycle-Finding Algorithm to detect a loop in a linked list in Java :
public class Main {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public static void main(String[] args) {
// Create a linked list with a loop
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = head.next;
System.out.println("Using Floyd's Cycle-Finding Algorithm: " + hasCycleFloyd(head));
}
// Floyd's Cycle-Finding Algorithm
public static boolean hasCycleFloyd(Node head) {
if (head == null || head.next == null) {
return false;
}
Node slow = head;
Node fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
Output :
Using Floyd's Cycle-Finding Algorithm: true
Explanation :
In this code we have uses Floyd’s Cycle-Finding Algorithm to detect a loop in a linked list. The algorithm starts with two pointers, slow and fast, both pointing to the head of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a loop in the linked list, the fast pointer will eventually catch up with the slow pointer, at which point we return true to indicate that a loop was detected. If there is no loop, the fast pointer will reach the end of the linked list and return false to indicate that a loop was not detected.
Example of using a HashSet to detect a loop in a linked list in Java :
import java.util.*;
public class Main {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public static void main(String[] args) {
// Create a linked list with a loop
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = head.next;
System.out.println("Using HashSet: " + hasCycleHashSet(head));
}
// HashSet
public static boolean hasCycleHashSet(Node head) {
Set nodes = new HashSet<>();
while (head != null) {
if (nodes.contains(head)) {
return true;
}
nodes.add(head);
head = head.next;
}
return false;
}
}
Output :
Using HashSet: true
Explanation :
In this code we have uses a HashSet to detect a loop in a linked list. The idea is to traverse the linked list and add each node to a HashSet as we go. If we encounter a node that is already in the HashSet, we know that we have encountered a loop, and we return true to indicate that a loop was detected. If we reach the end of the linked list without encountering a node that is already in the HashSet, we return false to indicate that a loop was not detected.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment