Detect loop in a linked list | Python3 program to return first node of loop A binary tree node has data , pointer to left child and a pointer to right child Helper function that allocates a new node with the given data and None left and right pointers ; A utility function to pra linked list ; Function to detect first node of loop in a linked list that may contain loop ; Create a temporary node ; This condition is for the case when there is no loop ; Check if next is already pointing to temp ; Store the pointer to the next node in order to get to it in the next step ; Make next poto temp ; Get to the next node in the list ; Driver Code ; Create a loop for testing ( 5 is pointing to 3 )
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def printList ( head ) : NEW_LINE INDENT while ( head != None ) : NEW_LINE INDENT print ( head . key , end = " ▁ " ) NEW_LINE head = head . next NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def detectLoop ( head ) : NEW_LINE INDENT temp = " " NEW_LINE while ( head != None ) : NEW_LINE INDENT if ( head . next == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( head . next == temp ) : NEW_LINE INDENT return True NEW_LINE DEDENT nex = head . next NEW_LINE head . next = temp NEW_LINE head = nex NEW_LINE DEDENT return False NEW_LINE DEDENT head = newNode ( 1 ) NEW_LINE head . next = newNode ( 2 ) NEW_LINE head . next . next = newNode ( 3 ) NEW_LINE head . next . next . next = newNode ( 4 ) NEW_LINE head . next . next . next . next = newNode ( 5 ) NEW_LINE head . next . next . next . next . next = head . next . next NEW_LINE found = detectLoop ( head ) NEW_LINE if ( found ) : NEW_LINE INDENT print ( " Loop ▁ Found " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ Loop " ) NEW_LINE DEDENT