Java Program to Detect loop in the LinkedList

May 24, 2023

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;
}

abs() Function

acos() Function

addExact() Function

asin() Function

atan() Function

java mob gif
java desk gif
  • 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 :

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
    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 :

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
    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 Prime

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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout