Loop detection in a linked list

In this post, we will discuss about the different algorithm for loop detection in a linked list.

Before writing the logic for loop detection in a linked list, we should understand the type and properties of the input parameter of this problem. We need a composite linked list consist of a singly linked list connected with a singly circular linked list. Below is the node structure of a given composite linked list.

Now, we are going to discuss two techniques by which we can detect the loop in a given composite linked list and count the number of nodes in loop.

1. Hashing : In Hashing technique, put all the node addresses into a HashSet and check if the node is available in HashSet. If yes, then loop detected in a composite linked list and stop moving to the next node. If no, then add the address into HashSet and move to the next node.This technique is good in case of less number of nodes in composite linked list, but if number of nodes in composite linked list is very huge, performance will be poor because we need to traverse through all the nodes to check the loop.
2. Floyd’s loop detection algorithm: According to Floyd’s loop detection algorithm, if slow moving pointer and fast moving pointer meet at some common point then there is a loop in a linked list. Definition of slow moving pointer and fast moving pointer refers, when a pointer move to the next consecutive node, that is called slow moving pointer. When a pointer skip the next consecutive node and move to the next of next node, that is called fast moving pointer.

Below is the code snippet to detect loop in a linked list using Hashing and Floyd’s loop detection algorithm.

Node.java

```package com.netSurfingZone.linkedList.misc;

public class Node<T> {

private T data ;

private Node<T> next;

public Node(T data) {
this.data = data;
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public Node<T> getNext() {
return next;
}

public void setNext(Node<T> next) {
this.next = next;
}

}
```

```package com.netSurfingZone.linkedList.misc;

private int size = 0;
private Node<T> node;

/**
*
* @param data
*/
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNext(newNode);
}
size++;
}

public void add(Node<T> newNode,int connectedNodes) {
if (newNode == null) {
return;
}
if (node == null) {
node = newNode;
} else {
Node<T> lastNode = getLastNode(node);
lastNode.setNext(newNode);
}
size=size + connectedNodes;
}

public Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}

private Node<T> next(Node<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}

public int size() {
return this.size;
}

private Node<T> getLastNode(Node<T> node) {

Node<T> lastNode = node;
if (lastNode.getNext() != null) {
return getLastNode(lastNode.getNext());
} else {
return lastNode;
}
}
}
```

```package com.netSurfingZone.linkedList.misc;

private int size = 0;
private Node<T> rootNode;
private Node<T> lastNode;

/**
*
* @param data
*/
if (data == null) {
return;
}
/**
* if circular linked list is empty and trying to add data, newly created node will be the
* root node and root node and last node will be same.
*/
if (rootNode == null) {
rootNode = new Node<T>(data);
lastNode=rootNode;
// connect last node to root node
lastNode.setNext(rootNode);
} else {
Node<T> newNode = new Node<T>(data);
lastNode.setNext(newNode);
lastNode=newNode;
// Last node will again connected to first Node;
lastNode.setNext(rootNode);
}
size++;
}

public Node<T> getRootNode(){
return this.rootNode;
}

public int size() {
return this.size;
}

private Node<T> next(Node<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}
}
```

```package com.netSurfingZone.linkedList.misc;

import java.util.HashSet;

public static void main(String[] args) {

//          A-->B-->C-->D-->E-->F-->G-->
//                       ^              |
//                       |______________|

System.out.println("Loop Detected using Hashing: " +loopDetected);

System.out.println(" ");
System.out.println("**********FLOYD LOOP DETECTION**********");
System.out.println("Number of nodes present in Loop: "+ NoOfNodesPresentInLoop);
}
/**
* Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point.
*  If slow_pointer and fast_pointer meet at some point then there is a loop
*
*/
System.out.println("No Loop Found");
return 0;
}

while(slow_pointer !=null && fast_Pointer !=null && fast_Pointer.getNext() !=null) {
slow_pointer=slow_pointer.getNext();
fast_Pointer=fast_Pointer.getNext().getNext();
// Loop found
if(slow_pointer !=null && fast_Pointer.getNext() !=null && slow_pointer == fast_Pointer) {
System.out.println("Loop Found");
return countNodes(slow_pointer);
}

}
System.out.println("No Loop Found");
return 0;
}
//Returns number of nodes present in loop.
private static int countNodes(Node n) {

int res = 1;
Node temp = n;
while (temp.getNext() != n)
{
res++;
temp = temp.getNext();
}
return res;

}
/**
* Put all the node addresses into HashSet and check if the node is exists in HashSet , if yes then loop found.
* if No , add the address in HashSet and check for next node.
*
*/
HashSet<Node> hash=new HashSet<>();
return false;
}
if(firstNode!=null) {
}
return true;
}
else {
}
}
return false;

}

}
```

Console Output:

Loop Detected using Hashing: true

**********FLOYD LOOP DETECTION**********
Loop Found
Number of nodes present in Loop: 4