Check linked list with a loop is palindrome or not | Node class ; Function to find loop starting node . loop_node - . Pointer to one of the loop nodes head - . Pointer to the start node of the linked list ; Count the number of nodes in loop ; Fix one pointer to head ; And the other pointer to k nodes after head ; Move both pointers at the same pace , they will meet at loop starting node ; This function detects and find loop starting node in the list ; Start traversing list and detect loop ; If slow_p and fast_p meet then find the loop starting node ; Return starting node of loop ; Utility function to check if a linked list with loop is palindrome with given starting point . ; Traverse linked list until last node is equal to loop_start and store the elements till start in a stack ; Traverse linked list until last node is equal to loop_start second time ; Compare data of node with the top of stack If equal then continue ; Else return False ; Return True if linked list is palindrome ; Function to find if linked list is palindrome or not ; Find the loop starting node ; Check if linked list is palindrome ; Driver code ; Create a loop for testing
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def getLoopstart ( loop_node , head ) : NEW_LINE INDENT ptr1 = loop_node NEW_LINE ptr2 = loop_node NEW_LINE k = 1 NEW_LINE i = 0 NEW_LINE while ( ptr1 . next != ptr2 ) : NEW_LINE INDENT ptr1 = ptr1 . next NEW_LINE k = k + 1 NEW_LINE DEDENT ptr1 = head NEW_LINE ptr2 = head NEW_LINE i = 0 NEW_LINE while ( i < k ) : NEW_LINE INDENT ptr2 = ptr2 . next NEW_LINE i = i + 1 NEW_LINE DEDENT while ( ptr2 != ptr1 ) : NEW_LINE INDENT ptr1 = ptr1 . next NEW_LINE ptr2 = ptr2 . next NEW_LINE DEDENT return ptr1 NEW_LINE DEDENT def detectAndgetLoopstarting ( head ) : NEW_LINE INDENT slow_p = head NEW_LINE fast_p = head NEW_LINE loop_start = None NEW_LINE while ( slow_p != None and fast_p != None and fast_p . next != None ) : NEW_LINE INDENT slow_p = slow_p . next NEW_LINE fast_p = fast_p . next . next NEW_LINE if ( slow_p == fast_p ) : NEW_LINE INDENT loop_start = getLoopstart ( slow_p , head ) NEW_LINE break NEW_LINE DEDENT DEDENT return loop_start NEW_LINE DEDENT def isPalindromeUtil ( head , loop_start ) : NEW_LINE INDENT ptr = head NEW_LINE s = [ ] NEW_LINE count = 0 NEW_LINE while ( ptr != loop_start or count != 1 ) : NEW_LINE INDENT s . append ( ptr . data ) NEW_LINE if ( ptr == loop_start ) : NEW_LINE INDENT count = 1 NEW_LINE DEDENT ptr = ptr . next NEW_LINE DEDENT ptr = head NEW_LINE count = 0 NEW_LINE while ( ptr != loop_start or count != 1 ) : NEW_LINE INDENT if ( ptr . data == s [ - 1 ] ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT if ( ptr == loop_start ) : NEW_LINE INDENT count = 1 NEW_LINE DEDENT ptr = ptr . next NEW_LINE DEDENT return True NEW_LINE DEDENT def isPalindrome ( head ) : NEW_LINE INDENT loop_start = detectAndgetLoopstarting ( head ) NEW_LINE return isPalindromeUtil ( head , loop_start ) NEW_LINE DEDENT def newNode ( key ) : NEW_LINE INDENT temp = Node ( 0 ) NEW_LINE temp . data = key NEW_LINE temp . next = None NEW_LINE return temp NEW_LINE DEDENT head = newNode ( 50 ) NEW_LINE head . next = newNode ( 20 ) NEW_LINE head . next . next = newNode ( 15 ) NEW_LINE head . next . next . next = newNode ( 20 ) NEW_LINE head . next . next . next . next = newNode ( 50 ) NEW_LINE head . next . next . next . next . next = head . next . next NEW_LINE if ( isPalindrome ( head ) == True ) : NEW_LINE INDENT print ( " Palindrome " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ Palindrome " ) NEW_LINE DEDENT