<p>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.</p>
<h2>Algorithms related to the Singly Linked list</h2>
<p>There are the following algorithms, we have discussed related to the singly linked list</p>
<blockquote>
<ul>
<li><strong><a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">Find the nth node from the end of a singly linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/find-the-middle-element-in-a-linked-list/">Find the middle element in a linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/reverse-linked-list/">How to Reverse linked list in Java</a></strong></li>
<li><strong><a href="https://dineshonjava.com/delete-given-node-from-singly-linked-list/">Delete given node from a singly linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/remove-duplicates-from-the-unsorted-singly-linked-list/">Remove Duplicates from the Unsorted Singly Linked list</a></strong></li>
</ul>
</blockquote>
<h2>Detect loop in a linked list</h2>
<p>Let&#8217;s see the following diagram of the singly linked list:<br />
<img class="aligncenter wp-image-4278 size-full" src="https://dineshonjava.com/wp-content/uploads/2018/09/Linked-List-Loop.png" alt="Detect loop in a linked list" width="583" height="228" /></p>
<p>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.</p>
<h3>Approach 1: Using Hashing</h3>
<p>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.</p>
<h3>Approach 2: Using Fast and Slow pointers</h3>
<p>This is a very efficient approach to detect a loop in a linked list.</p>
<p><strong>Step 1:</strong> Let&#8217;s take two pointers slow and fast.<br />
<strong>Step 2:</strong> Intialize both pointers slow = head and fast = head.next.next.<br />
<strong>Step 3:</strong> Navigate both pointers, slow pointer moves one node at a time but fast pointer moves two nodes a time.<br />
<strong>Step 4:</strong> If both pointers meet at some point, we have found the loop.<br />
<strong>Step 5:</strong> Now find the loop length<br />
<strong>Step 6:</strong> At the point where both pointers have met, stop one pointer and keep moving the another one<br />
<strong>Step 7:</strong> When another pointer meets the first pointer, stop.<br />
<strong>Step 8:</strong> Keep counting number of hops, that will your loop length</p>
<p>Let&#8217;s see the complete code for this algorithm.</p>
<pre>package com.dineshonjava.algo.linkedlist; 
 
/** 
 * @author Dinesh.Rajput 
 * 
 */ 
public class Node { 
	 
 Node next; 
 String data; 
 
 public Node(String data) { 
	super(); 
	this.data = data; 
 } 
} 
 
</pre>
<p>Code for loop detection in the linked list<br />
<strong>LoopInLinkedList.java</strong></p>
<pre>/** 
 * 
 */ 
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; 
	} 
 
} 
 
</pre>
<p>Run above program, you will get the following <strong>output</strong>:</p>
<pre>Loop Found in Linked List 
Length of Loop is 5 
</pre>
<p>In this example, we have written a program to detect a loop in a linked list</p>
<p>Hope, you have understood this solution. Please share other solutions if you have. :).</p>
<p>Happy learning with us!!!.</p>
<div align="center"><iframe style="width: 120px; height: 240px;" src="//ws-in.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&;OneJS=1&;Operation=GetAdHtml&;MarketPlace=IN&;source=ac&;ref=tf_til&;ad_type=product_link&;tracking_id=dineshonjav06-21&;marketplace=amazon&;region=IN&;placement=1787127567&;asins=1787127567&;linkId=a1e64f621b5e6128d8cb10e876eb1c48&;show_border=true&;link_opens_in_new_window=true&;price_color=333333&;title_color=0066c0&;bg_color=ffffff" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" align="center"><span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span><br />
</iframe></div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/remove-duplicates-from-the-unsorted-singly-linked-list/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/find-and-break-a-loop-in-a-linked-list/">Next</a> 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '4277'});
});
</script>
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…