How to remove loop in LinkedList in Java ?

In this post, we will learn How to remove loop in LinkedList in Java. This problem statement is the extension of the below problems:

How to check whether a linked list has a loop/cycle in java ?
Find start node of the loop in Singly LinkedList in java

After removing loop from Above image shown output should be:2 5 8 40 10 90

In order to remove a loop from LinkedList we have to follow below three steps:

First, we have to check whether a loop exists in a linked list or not.

Steps for checking whether LinkedList has loop or cycle is not are as follows-

We use 2 references(slowReference & fastReference ) which are initialized to the head of the linked list.
slowReference hop a node and the fastReference takes two hops in each iteration.
If both of these references point to the same node at some iteration that means there is a loop.
If any of these two references pointing to null that means there is no loop in the linked list.

If we find that loop exists then both pointers will meet at some node. From there we will have to find the start node of the loop.

First of all, we have to find a meeting point for slowReference and fastReference.
Next Step to set slowReference to head node of LinkedList.
Afterward move slowReference and fastReference both by one node at a time
The node at which slowReference and fastReference meets that will be starting node of the loop.

Once both slowReference and fastReference are at the beginning of the loop if you move fastReference by one node at a time ultimately it will again become equal to slowReference as it will cycle back because of the loop. That location of the fastReference where it becomes equal to the slowReference again is the end node of the loop. To remove the loop in the LinkedList. We have to just set the next to null for the node referenced by fastReference .

Below is the complete Source code:

package com.kkjavatutorials.util;
 
/**
 *How to remove loop in LinkedList in Java
 * @author KK JavaTutorials
 */
public class LinkedList<T> {
 
	//head Node of LinkedList
	private Node<T> head;
	
	//This inner class represent Node in Linked List
	private static class Node<T>{
		private T data;
		private Node<T> next;
	
		public Node(T data) {
			super();
			this.data = data;
			this.next = null;
		}
	}
	
	//Method to insert Node in Linked List
	public void insert(Node<T> newNode) {
		if(isEmpty()) {
			head = newNode;
		}else {
			Node<T> current = head;
			while(current.next !=null) {
				current = current.next;
			}
			
			current.next =  newNode;
		}
	}
 
	//Check if Linked is empty
	private boolean isEmpty() {
		return head == null;
	}
	
	//Method to display linked List
	public void displayLinkedList() {
		Node<T> current = head;
		while(current !=null) {
			System.out.print(current.data+" ");
			current = current.next;
		}
	}
	
	//Method to check whether LinkedList has loop/cycle or not
	public boolean isCyclicLinkedList() {
		Node<T> slowReference = head;
		Node<T> fastReference = head;
		
		while (slowReference != null && fastReference !=null && fastReference.next != null) {
			fastReference = fastReference.next.next;
			slowReference = slowReference.next;
			
			if(slowReference == fastReference)
				return true;
		}
		return false;
	}
	
	/**
	 * Function to find start node of loop in 
	 * Singly LinkedList in java 
	 * @return Start node of loop in LinkedList
	 */
	public Node<T> findStartNodeOfTheLoop() {
 
		boolean isLoop = false;
 
		Node<T> fastReference = head;
		Node<T> slowReference = head;
 
		while (fastReference != null && fastReference.next != null) {
			fastReference = fastReference.next.next;
			slowReference = slowReference.next;
			if (slowReference == fastReference) {
				isLoop = true;
				break;
			}
 
		}
		if (isLoop) {
			slowReference = head;
			while (slowReference != fastReference) {
				slowReference = slowReference.next;
				fastReference = fastReference.next;
			}
		} else {
			slowReference = null;
		}
		return slowReference;
	}
	
	/**
	 * Function to remove loop in LinkedList
	 * @param startNode of LinkedList
	 */
	public void removeLoopFromLinkedList(Node<T> startNode) {
		Node<T> fastReference = startNode;
		Node<T> slowReference = startNode;

		while (fastReference.next != slowReference) {
			fastReference = fastReference.next;
		}
		fastReference.next = null;
	}
	
	
	public static void main(String[] args) {
		Node<Integer> node = new Node<Integer>(2);
		
		LinkedList<Integer> linkedList = new LinkedList<>();
		
		linkedList.insert(node);
		linkedList.insert(new Node<Integer>(5));
		linkedList.insert(new Node<Integer>(8));
		linkedList.insert(new Node<Integer>(40));
		linkedList.insert(new Node<Integer>(10));
		linkedList.insert(new Node<Integer>(90));
		linkedList.insert(node);
		
		boolean cyclicLinkedList = linkedList.isCyclicLinkedList();
		if(cyclicLinkedList)
			System.out.println("Loop is detected in LinkedList");
		else
			System.out.println("Loop is not detected in LinkedList");
		
		Node<Integer> findStartNodeOfTheLoop = linkedList.findStartNodeOfTheLoop();
		if(findStartNodeOfTheLoop != null)
		System.out.println("Start node of the loop in Singly LinkedList is:"+findStartNodeOfTheLoop.data);
		
		/*Before Removing loop from LinkedList
		 * If you try to display LinkedList then it will go
		 * in infinite loop. To test it just un-comment line of code*/
		//linkedList.displayLinkedList();
		
		if(findStartNodeOfTheLoop != null) {
			System.out.println("After removing the loop from LinkedList:");
			linkedList.removeLoopFromLinkedList(findStartNodeOfTheLoop);
			linkedList.displayLinkedList();
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147