Detect loop in a linked list | Link list node ; allocate node ; put in the data ; link the old list off the new node ; move the head to point to the new node ; Returns true if there is a loop in linked list else returns false . ; If this node is already traverse it means there is a cycle ( Because you we encountering the node for the second time ) . ; If we are seeing the node for the first time , mark its flag as 1 ; Driver program to test above function ; Start with the empty list ; Create a loop for testing
class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . next = None NEW_LINE self . flag = 0 NEW_LINE DEDENT DEDENT def push ( head_ref , new_data ) : NEW_LINE INDENT new_node = Node ( ) ; NEW_LINE new_node . data = new_data ; NEW_LINE new_node . flag = 0 ; NEW_LINE new_node . next = ( head_ref ) ; NEW_LINE ( head_ref ) = new_node ; NEW_LINE return head_ref NEW_LINE DEDENT def detectLoop ( h ) : NEW_LINE INDENT while ( h != None ) : NEW_LINE INDENT if ( h . flag == 1 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT h . flag = 1 ; NEW_LINE h = h . next ; NEW_LINE DEDENT return False ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT head = None ; NEW_LINE head = push ( head , 20 ) ; NEW_LINE head = push ( head , 4 ) ; NEW_LINE head = push ( head , 15 ) ; NEW_LINE head = push ( head , 10 ) NEW_LINE head . next . next . next . next = head ; NEW_LINE if ( detectLoop ( head ) ) : NEW_LINE INDENT print ( " Loop ▁ found " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ Loop " ) NEW_LINE DEDENT DEDENT