Detect loop in a linked list

This tutorial is all about how to find a loop in a linked list. But, before we must know What is LinkedList?

Loop in a Linked-List: While traversing the list if you didn’t reach NULL which means the last node in the list or we found that the node is already visited then its a loop in list. It is also called circular LinkedList.

The circular linked list is a linked list that never ends because of a node next having the address of the first node (from where we start) or the middle node (already visited node).

To detect, we need to traverse the whole LinkedList using Floyd’s Cycle-Finding Algorithm.
Algo Steps:
1. Traverse the complete list using two pointer approach, one is a slow pointer(sloP) and second is the fast pointer(faP).
2. Slow pointer(sloP) traverse by one jump at a time and fast pointer(faP) traversed by two jumps at a time.
3. While traversing if both slow and fast pointers are meet at the same node then its a loop but instead of, one of them reach Null then there is no loop.

boolean detectLoop() {
     
     Node sloP = head, faP = head;	
     while(sloP != null && faP !=null && faP.next !=null) {
	  sloP = sloP.next;
	  faP  = faP.next.next;
	  if(sloP  == faP) {
	     System.out.println(" Loop Found ");
	     return true;
         }
     }
     return false;
}

Floyd’s Cycle-Finding Algorithm is an efficient approach to detect a loop in a list.

Time Complexity: O(n)
Auxiliary Space: O(1)