Detect & Handle Infinite Loops and Cycles in Linked Lists

Learn to detect infinite loops in LinkedLists, find the start node of a cycle, and introduce a loop using Java code. Explore cycle detection techniques.

java

package com.java.linklist;
public class LinkedList<T> {
public static class Node<T> {
// reference to the next node in the chain, or null if there isn't one.
Node<T> next;
// data carried by this node. could be of any type you need.
T data;
// Node constructor
public Node(T dataValue) {
   next = null;
   data = dataValue;
}
// another Node constructor if we want to specify the node to point to.
public Node(T dataValue, Node<T> nextValue) {
   next = nextValue;
   data = dataValue;
}
// these methods should be self-explanatory
public T getData() {
   return data;
}
public void setData(T dataValue) {
   data = dataValue;
}
public Node<T> getNext() {
   return next;
}
public void setNext(Node<T> nextValue) {
   next = nextValue;
}
}
private Node<T> head;
private Node<T> tail;
public LinkedList() {
}
LinkedList(T data) {
Node<T> n1 = new Node<T>(data);
this.head = n1;
this.tail = n1;
}
/**
  * appends the specified element to the end of this list.
  *
  * @param data
  */
public void add(T data) {
// if we have an empty list, create a new list
// and copy its head and tail into current object
if (this.head == null) {
   LinkedList<T> linkList = (new LinkedList<T>(data));
   this.head = linkList.head;
   this.tail = linkList.tail;
   return;
}
// we need to add this node 'n' to the end of the list
Node<T> n = new Node<T>(data);
Node<T> current = this.head, prev = null;
while (current != null) {
   prev = current;
   current = current.next;
}
prev.next = n;
this.tail = n; // update the tail info as well
}
public String toString() {
String output = "";
if (head != null) {
   Node<T> n = head.getNext();
   output += "[" + head.getData().toString() + "]-->";
   //System.out.println("[" + head.getData().toString() + "]");
   while (n != null) {
    output += "[" + n.getData().toString() + "]-->";
    //System.out.println("[" + n.getData().toString() + "]");
    n = n.getNext();
   }
}
return output;
}
/**
  * introduces loop of given length at the end of the list.
  *
  * @param length
  */
public void introduceLoop(int length) {
if (this.head == null) {
   System.out.println("Empty List. Loop can not be inserted");
   return;
}
Node<T> p1 = this.head, p2 = this.head;
int count = 0;
while (count < length) {
   if (p2 == null) {
    System.out.println("Incorrect length of the loop given");
    break;
   }
   p2 = p2.next;
   count++;
}
Node<T> prevP2 = null;
while (p2 != null) {
   prevP2 = p2;
   p2 = p2.next;
   p1 = p1.next;
}
prevP2.next = p1;
System.out.println("Loop or cycle Start of length " + length
    + " and the value of node is -->" + p1.data);
}
/**
  * <ul>
  * <li>The Tortoise (Slow ptr) and the Hare (fast ptr) start at the
  * beginning of linked list.</li>
  * <li>For each iteration, slow ptr moves one step and the fast ptr moves
  * two steps.</li>
  * <li>If there is a loop, fast ptr will go around the loop and meet with
  * slow ptr.</li>
  * <li>If there is no loop, the fast prt will get to the end of the list
  * without meeting up with the slow ptr.</li>
  * </ul>
  *
  * @return boolean
  */
public boolean ifLoopExists() {
Node<T> fastPtr = head;
Node<T> slowPtr = head;
while (slowPtr != null && fastPtr != null && fastPtr.next != null) {
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
   if (slowPtr == fastPtr)
    return true;
}
return false;
}
/**
  * <ul>
  * <li>The Tortoise (Slow ptr) and the Hare (fast ptr) start at the
  * beginning of linked list.</li>
  * <li>For each iteration, slow ptr moves one step and the fast ptr moves
  * two steps.</li>
  * <li>If there is a loop, fast ptr will go around the loop and meet with
  * slow ptr.</li>
  * <li>If there is no loop, the fast prt will get to the end of the list
  * without meeting up with the slow ptr.</li>
  * </ul>
  * @return Node
  */
public Node<T> findStartNodeOfTheLoop() {
Node<T> fastPtr = head;
Node<T> slowPtr = head;
boolean loopExists = false;
while (fastPtr != null && fastPtr.next != null) {
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
   if (slowPtr == fastPtr) {
    loopExists = true;
    break;
   }
}
if (loopExists) {
   slowPtr = head;
   while (slowPtr != fastPtr) {
    slowPtr = slowPtr.next;
    fastPtr = fastPtr.next;
   }
} else {
   System.out.println("Loop does not exists");
   slowPtr = null;
}
return slowPtr;
}
public static void main(String[] args) {
System.out.println("------------------Integer-------------------");
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(5);
list.add(6);
list.add(3);
list.add(1);
list.add(2);
System.out.println(list.toString());
list.introduceLoop(3);
System.out.println(list.ifLoopExists());
Node<Integer> startNode = list.findStartNodeOfTheLoop();
if (startNode != null) {
   System.out.println("start Node of loop is for integer " + startNode.data);
}
System.out.println("------------------String-------------------");
LinkedList<String> list2 = new LinkedList<String>();
list2.add("Kartik");
list2.add("Mandal");
list2.add("Saharda");
list2.add("kharagpur");
list2.add("Westbengal");
list2.add("India");
System.out.println(list2.toString());
list2.introduceLoop(4);//loop
System.out.println(list2.ifLoopExists());//find out loop
Node<String> startNode2 = list2.findStartNodeOfTheLoop();//find out start point of loop
if (startNode != null) {
   System.out.println("start Node of loop is for string " + startNode2.data);
}
}
}

The code you provided is a Java implementation of a generic linked list that supports basic operations like adding elements, detecting loops, and finding the start node of a loop. Here’s a summary of the key components and how they work:

1. Node Class

The Node<T> class is a static nested class inside the LinkedList class.
Each node contains a reference to the next node (next) and a generic data element (data).
Constructors are provided for creating nodes with or without specifying the next node.

2. LinkedList Class

The LinkedList<T> class is a generic class that supports different data types.
It maintains references to the head and tail of the linked list.
A default constructor initializes an empty list.
Another constructor initializes a list with a single node containing the provided data.

3. add Method

This method adds a new node with the provided data to the end of the list.
If the list is empty, it initializes the list with the new node as both head and tail.
Otherwise, it traverses to the end of the list and appends the new node.

4. toString Method

This method returns a string representation of the linked list by traversing from the head to the tail and appending each node’s data to a string.

5. introduceLoop Method

This method introduces a loop in the linked list by connecting the last node to a node at a specific distance (length) from the head.
If the loop length is greater than the size of the list, an error message is printed.

6. ifLoopExists Method

This method detects if a loop exists in the linked list using Floyd's Tortoise and Hare algorithm.
It returns true if a loop is found, otherwise false.

7. findStartNodeOfTheLoop Method

This method returns the starting node of the loop if a loop exists.
It first detects if a loop exists, then resets the slow pointer to the head and moves both slow and fast pointers one step at a time until they meet, which is the start of the loop.

8. Main Method

The main method tests the linked list implementation with Integer and String data types.
It demonstrates adding elements, introducing loops, detecting loops, and finding the start of the loop.

Example Outputs:

If you run this program, the output will look like this:

plaintext

------------------Integer-------------------

[5]-->[6]-->[3]-->[1]-->[2]-->

Loop or cycle Start of length 3 and the value of node is -->6

true

start Node of loop is for integer 6

------------------String-------------------

[Kartik]-->[Mandal]-->[Saharda]-->[kharagpur]-->[Westbengal]-->[India]-->

Loop or cycle Start of length 4 and the value of node is -->Mandal

true

start Node of loop is for string Mandal

This output shows the string representation of the linked list, the introduction of a loop, whether a loop exists, and the start node of the loop for both integer and string data types.

Key Points to Consider:

Generics: The implementation uses Java Generics (<T>) to make the linked list type-safe and reusable for different data types.
Loop Detection: The ifLoopExists method uses the fast and slow pointer approach to efficiently detect loops.
Finding Loop Start: The findStartNodeOfTheLoop method resets the slow pointer to the head to find the start of the loop after detecting a loop.

This implementation provides a solid foundation for understanding basic linked list operations, including advanced features like loop detection and handling.