Find start node of loop in Singly LinkedList in java?

In a couple of previous Posts, We already went through the Singly Linked List Problem statements:

Implementing a Circular Singly Linked List in Java ?
How to check whether a linked list has a loop/cycle in java ?

In this post, We will learn How to find start a node of loop in Singly LinkedList in java?

The logic used in this Program:

First of all, we have to find a meeting point of 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.

Below is the complete source code:

package com.kkjavatutorials.util;

/**
 * Find start node of loop in Singly LinkedList in java ?
 *  @author KK JavaTutorials
 */
public class LinkedList<T> {
	
	private Node<T> head;
	
	//This internal class represents 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;
		}
	}
	
	/**
	 * This method insert a Node in Linked List
	 * @param newNode has to insert in the List
	 */
	public void insert(Node<T> newNode) {
		if(head == null) {
			head = newNode;
		}else {
			Node<T> currentNode = head;
			while (currentNode.next != null) {
				currentNode = currentNode.next;
			}
			 currentNode.next = newNode;
		}
	}
	
	/**
	 * Method 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;
	}
 
	public static void main(String[] args) {
		
		Node<Integer> node1 = new Node<Integer>(10);
		Node<Integer> node2 = new Node<Integer>(20);
		Node<Integer> node3 = new Node<Integer>(30);
		
		Node<Integer> node4 = new Node<Integer>(40);
		
		Node<Integer> node5 = new Node<Integer>(50);
		Node<Integer> node6 = new Node<Integer>(60);
		Node<Integer> node7 = new Node<Integer>(70);
		
		LinkedList<Integer> linkedList = new LinkedList<>();
		linkedList.insert(node1);
		linkedList.insert(node2);
		linkedList.insert(node3);
		
		//Node with value 40 added first time
		linkedList.insert(node4);
		linkedList.insert(node5);
		linkedList.insert(node6);
		linkedList.insert(node7);
		
		//Node with value 40 added Second time
		linkedList.insert(node4);
		
		Node<Integer> loopNode = linkedList.findStartNodeOfTheLoop();
		if(loopNode != null) {
			System.out.println("Start node of loop in Singly LinkedList = "+loopNode.data);
		}else {
			System.out.println("Loop does not exists in Linked List!!");
		}
	}
}

100

101

102

103