Algorithms

How to Detect loop in a linked list

In this article, we will discuss an algorithm on how to detect a loop in a linked list. So, in a given linked list, check whether it contains the loop in it, if yes then find the Loop length. As know that, a singly linked list has several nodes, and each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node.

Algorithms related to the Singly Linked list

There are the following algorithms, we have discussed related to the singly linked list

Detect loop in a linked list

Let’s see the following diagram of the singly linked list:

As you can see in the above diagram, loop in a linked list means the last node does not point to the null, instead it points to some node in the list. There are are several approaches to solve this problem.

Approach 1: Using Hashing

Navigate the linked list and put each node to the HashSet if the node is not present in the HashSet if node is present in the HashSet that means the given singly linked list has a loop.

Approach 2: Using Fast and Slow pointers

This is a very efficient approach to detect a loop in a linked list.

Step 1: Let’s take two pointers slow and fast.
Step 2: Intialize both pointers slow = head and fast = head.next.next.
Step 3: Navigate both pointers, slow pointer moves one node at a time but fast pointer moves two nodes a time.
Step 4: If both pointers meet at some point, we have found the loop.
Step 5: Now find the loop length
Step 6: At the point where both pointers have met, stop one pointer and keep moving the another one
Step 7: When another pointer meets the first pointer, stop.
Step 8: Keep counting number of hops, that will your loop length

Let’s see the complete code for this algorithm.

package com.dineshonjava.algo.linkedlist;

/**
 * @author Dinesh.Rajput
 *
 */
public class Node {
	
    Node next;
    String data;
    
    public Node(String data) {
	super();
	this.data = data;
    }
}

Code for loop detection in the linked list
LoopInLinkedList.java

/**
 * 
 */
package com.dineshonjava.algo.linkedlist;

/**
 * @author Dinesh.Rajput
 *
 */
public class LoopInLinkedList {
	
	public static void main(String[] args) {
		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 = new Node("5");
		head.next.next.next.next.next = new Node("6");
		head.next.next.next.next.next.next = new Node("7");
		head.next.next.next.next.next.next.next = head.next.next;
		findLoop(head);
	}
	
	private static void findLoop(Node head) {
		Node slow = head;
		Node fast = head.next.next;
		while(slow != null) {
			if(slow == fast) {
				System.out.println("Loop Found in Linked List");
				int lengthLoop = findLength(slow, fast);
				break;
			}else {
				slow = slow.next;
				fast = fast.next.next;
			}
		}
	}

	private static int findLength(Node firstPtr, Node secondPtr) {
		secondPtr = secondPtr.next;
		int lengthLoop = 1;
		while(secondPtr != firstPtr) {
			lengthLoop++;
			secondPtr = secondPtr.next;
		}
		System.out.println("Length of Loop is "+lengthLoop);
		return lengthLoop;
	}

}

Run above program, you will get the following output:

Loop Found in Linked List
Length of Loop is 5

In this example, we have written a program to detect a loop in a linked list

Hope, you have understood this solution. Please share other solutions if you have. :).

Happy learning with us!!!.

Previous
Next
Dinesh Rajput

Dinesh Rajput is the chief editor of a website Dineshonjava, a technical blog dedicated to the Spring and Java technologies. It has a series of articles related to Java technologies. Dinesh has been a Spring enthusiast since 2008 and is a Pivotal Certified Spring Professional, an author of a book Spring 5 Design Pattern, and a blogger. He has more than 10 years of experience with different aspects of Spring and Java design and development. His core expertise lies in the latest version of Spring Framework, Spring Boot, Spring Security, creating REST APIs, Microservice Architecture, Reactive Pattern, Spring AOP, Design Patterns, Struts, Hibernate, Web Services, Spring Batch, Cassandra, MongoDB, and Web Application Design and Architecture. He is currently working as a technology manager at a leading product and web development company. He worked as a developer and tech lead at the Bennett, Coleman & Co. Ltd and was the first developer in his previous company, Paytm. Dinesh is passionate about the latest Java technologies and loves to write technical blogs related to it. He is a very active member of the Java and Spring community on different forums. When it comes to the Spring Framework and Java, Dinesh tops the list!

Share
Published by
Dinesh Rajput

Recent Posts

Strategy Design Patterns using Lambda

Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…

2 years ago

Decorator Pattern using Lambda

Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…

2 years ago

Delegating pattern using lambda

Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…

2 years ago

Spring Vs Django- Know The Difference Between The Two

Technology has emerged a lot in the last decade, and now we have artificial intelligence;…

2 years ago

TOP 20 MongoDB INTERVIEW QUESTIONS 2022

Managing a database is becoming increasingly complex now due to the vast amount of data…

2 years ago

Scheduler @Scheduled Annotation Spring Boot

Overview In this article, we will explore Spring Scheduler how we could use it by…

3 years ago