4. Remove loop in linked list

4. Remove loop in linked list

Problem link :- click here

package Linked_List;

public class LinkedList__4
{
	/*
	 	This is similar to the previous problem but here we have to remove
	 	the loop.
	 */
	
	static Boolean removeLoop(LinkedList list)
	{
		if(list.head == null   ||   list.head.next == null)
			return true;
		
		Node slow = list.head;
		Node fast = list.head;
		
		//step 1 :- we will take one node from the loop
		while(fast!=null  &&  fast.next!=null)
		{
			slow = slow.next;
			fast = fast.next.next;
			
			if(slow.data  ==  fast.data)
				break;
		}
		
		//step 2 :- Now there are 2 cases, 
		//1-> full loop last node is pointing to first node. In that case both meets 
		//only at the head. In this case we will find the last node 
		//since we know it is pointing to the first node
		if(fast == list.head  &&  slow ==list.head)
		{
			while(fast.next  !=  list.head)
			{
				fast = fast.next;
			}
			fast.next = null;
			System.out.println("Loop has been removed. Now you can print");
			return true;
		}
		
		
		//step 2 :- 2-> In this case the starting node of the loop will be in the middle 
		//of the list. So we will iterate from two sides one from head  and other from 
		//a node inside the loop that we get from step 1.
		//here we will use slow to iterate from head instead of creating another node.
		slow = list.head;
		while(slow.next != fast.next)
		{
			slow = slow.next;
			fast = fast.next;
		}
		fast.next = null;
		System.out.println("Loop has been removed. Now you can print");
		return true;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(8);
		list.push(3);
		list.push(4);
		
		//creating a loop
		Node node = list.head.next.next.next;
		node.next = list.head.next;
		
		Boolean ans = removeLoop(list);
		if(ans)
			printList(list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

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