Detect loop in a linked list | Java program to return first node of loop ; A utility function to print a linked list ; returns distance between first and last node every time * last node moves forwars ; counts no of nodes between first and last ; Function to detect first node of loop in a linked list that may contain loop ; Create a temporary node ; first always points to head ; last pointer initially points to head ; current_length stores no of nodes between current * position of first and last ; current_length stores no of nodes between previous * position of first and last ; set prev_length to current length then update the current length ; distance is calculated ; last node points the next node ; Driver program to test above function ; Create a loop for testing ( 5 is pointing to 3 )
import java . util . * ; class GFG { static class Node { int key ; Node next ; } ; static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . next = null ; return temp ; } static void printList ( Node head ) { while ( head != null ) { System . out . print ( head . key + " ▁ " ) ; head = head . next ; } System . out . println ( ) ; } static int distance ( Node first , Node last ) { int counter = 0 ; Node curr ; curr = first ; while ( curr != last ) { counter += 1 ; curr = curr . next ; } return counter + 1 ; } static boolean detectLoop ( Node head ) { Node temp = new Node ( ) ; Node first , last ; first = head ; last = head ; int current_length = 0 ; int prev_length = - 1 ; while ( current_length > prev_length && last != null ) { prev_length = current_length ; current_length = distance ( first , last ) ; last = last . next ; } if ( last == null ) { return false ; } else { return true ; } } public static void main ( String [ ] args ) { Node head = newNode ( 1 ) ; head . next = newNode ( 2 ) ; head . next . next = newNode ( 3 ) ; head . next . next . next = newNode ( 4 ) ; head . next . next . next . next = newNode ( 5 ) ; head . next . next . next . next . next = head . next . next ; boolean found = detectLoop ( head ) ; if ( found ) System . out . print ( " Loop ▁ Found " ) ; else System . out . print ( " No ▁ Loop ▁ Found " ) ; } }