5. Find first node of the loop in the linked list

5. Find first node of the loop in the linked list

Problem link :- click here

package Linked_List;

public class LinkedList__5
{

	static Node findFirstNode(LinkedList list)
	{
		//we have solved this problem as a subproblem in the previous problem.
		//step 1 :- we will take one node from the loop
		Node slow = list.head;
		Node fast = list.head;
		while(fast.next != null   &&   fast.next.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
				
			if(slow.data == fast.data)
				break;
		}
		
		//Now there are two cases 
		//1 -> first node of the linked list is involved in the loop, 
		//then it is the first node of the loop.
		//If it is involved then high and low will be pointing to the first node.
		if(slow==list.head   &&   fast==list.head)
			return list.head;
		
		//2 -> First node of the loop will be in the middle of the linked list. 
		//Here we will traverse from two sides one is from the first node
		//and the other from the node inside the loop. 
		//NOTE :- THE NODE THAT WE GET INSIDE THE LOOP WILL BE
		// 'x' NODE AWAY FROM THE FIRST NODE OF THE LOOP.
		//where       x   -> number of nodes from first node of the linked list 
		//to reach the first node of the loop
		slow = list.head;
		while(slow.next != fast.next)
		{
			slow = slow.next;
			fast = fast.next;
		}
		Node ans = fast.next;
		
		return ans;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(2);
		list.push(3);
		list.push(4);
		list.push(5);
		
		//creating the loop
		list.head.next.next.next.next = list.head.next.next;
		
		Node ans = findFirstNode(list);
		System.out.println("First node of the loop is : " + ans.data);
	}

}

Time complexity :- O(n)
Space complexity :- O(1)