<p>In this article, we will discuss an algorithm on how to find and break 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 and break this loop. 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>
<li><strong><a href="https://dineshonjava.com/singly-linked-list-is-palindrome/">The singly linked list is palindrome without extra space</a></strong></li>
<li><strong><a href="https://dineshonjava.com/how-to-detect-loop-in-a-linked-list/">How to Detect loop in a linked list</a></strong></li>
</ul>
</blockquote>
<h2>Find and Break loop in a linked list</h2>
<p>Let’s see the following diagram of the singly linked list:</p>
<p><img class="aligncenter wp-image-4278 size-full" src="https://dineshonjava.com/wp-content/uploads/2018/09/Linked-List-Loop.png" alt="Find and Break a 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>
<h2>Approach to find and break loop in a linked list</h2>
<p>This is a very efficient approach to detect a loop in a linked list.</p>
<p><strong>Step 1:</strong> Let’s take two pointers <em>slow</em> and <em>fast</em>.<br />
<strong>Step 2:</strong> Intialize both pointers <em>slow = head and fast = head.next.next.</em><br />
<strong>Step 3:</strong> Navigate both pointers, the <em>slow</em> 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<br />
<strong>Step 9:</strong> Let&#8217;s break the loop<br />
<strong>Step 10</strong>: Move one pointer by the loop length from the head of the linked list<br />
<strong>Step 11:</strong> Another pointer fixes at the head and moves both pointers with normal speed.<br />
<strong>Step 12:</strong> When <em>ptr2.next = ptr1</em> pointer, set <em>ptr2.next=null</em></p>
<p>Let’s see the complete code for this algorithm.</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); 
		 
		display(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); 
				breakLoop(head, lengthLoop); 
				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; 
	} 
 
	private static void breakLoop(Node head, int lengthLoop) { 
		Node ptr1 = head; 
		Node ptr2 = head; 
		 
		while(lengthLoop >; 0) { 
			lengthLoop --; 
			ptr2 = ptr2.next; 
		} 
		while(ptr2 != ptr1) { 
			ptr2 = ptr2.next; 
			ptr1 = ptr1.next; 
		} 
		 
		 ptr2 = ptr2.next; 
		 while (ptr2.next != ptr1) { 
			 ptr2 = ptr2.next; 
		 } 
		ptr2.next = null; 
		System.out.println("Loop breaks"); 
	} 
	 
	private static void display(Node head){ 
 Node n=head; 
 while(n!=null){ 
 System.out.print("->;" + n.data); 
 n=n.next; 
 } 
	} 
} 
 
 
public class Node { 
	 
 Node next; 
 String data; 
 public Node(String data) { 
	super(); 
	this.data = data; 
 } 
} 
</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 
Loop breaks 
->;1->;2->;3->;4->;5->;6->;7 
</pre>
<p>In this example, we have written a program to find and break 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=qf_sp_asin_til&;ad_type=product_link&;tracking_id=dineshonjav06-21&;marketplace=amazon&;region=IN&;placement=1788299450&;asins=1788299450&;linkId=05b0146b0a85f4472697901e353dc276&;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"><br />
</iframe></div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/how-to-detect-loop-in-a-linked-list/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/internal-working-of-hashmap-in-java/">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: '4280'});
});
</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…