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) {
return false;
}

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<>();

return true;
}

}

return false;
}
```

Example of the Floyd’s Cycle-Finding Algorithm to detect a loop in a linked list in Java :

Run
```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

System.out.println("Using Floyd's Cycle-Finding Algorithm: " + hasCycleFloyd(head));
}

// Floyd's Cycle-Finding Algorithm
public static boolean hasCycleFloyd(Node head) {
return false;
}

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 :

Run
```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

}

// HashSet
public static boolean hasCycleHashSet(Node head) {
Set nodes = new HashSet<>();

return true;
}

}

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.

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