Function to check if a singly linked list is palindrome | Node class ; Function to initialize head ; Function to check if given linked list is pallindrome or not ; To handle odd size list ; Initialize result ; Get the middle of the list . Move slow_ptr by 1 and fast_ptrr by 2 , slow_ptr will have the middle node ; We need previous of the slow_ptr for linked lists with odd elements ; fast_ptr would become NULL when there are even elements in the list and not NULL for odd elements . We need to skip the middle node for odd case and store it somewhere so that we can restore the original list ; Now reverse the second half and compare it with first half ; NULL terminate first half ; Reverse the second half ; Compare ; Reverse the second half again ; If there was a mid node ( odd size case ) which was not part of either first half or second half . ; Function to reverse the linked list Note that this function may change the head ; Function to check if two input lists have same data ; Both are empty return 1 ; Will reach here when one is NULL and other is not ; Function to insert a new node at the beginning ; Allocate the Node & Put in the data ; Link the old list off the new one ; Move the head to point to new Node ; A utility function to print a given linked list ; Driver code ; Start with the empty list
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT class LinkedList : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . head = None NEW_LINE DEDENT def isPalindrome ( self , head ) : NEW_LINE INDENT slow_ptr = head NEW_LINE fast_ptr = head NEW_LINE prev_of_slow_ptr = head NEW_LINE midnode = None NEW_LINE res = True NEW_LINE if ( head != None and head . next != None ) : NEW_LINE INDENT while ( fast_ptr != None and fast_ptr . next != None ) : NEW_LINE INDENT fast_ptr = fast_ptr . next . next NEW_LINE prev_of_slow_ptr = slow_ptr NEW_LINE slow_ptr = slow_ptr . next NEW_LINE DEDENT if ( fast_ptr != None ) : NEW_LINE INDENT midnode = slow_ptr NEW_LINE slow_ptr = slow_ptr . next NEW_LINE DEDENT second_half = slow_ptr NEW_LINE prev_of_slow_ptr . next = None NEW_LINE second_half = self . reverse ( second_half ) NEW_LINE res = self . compareLists ( head , second_half ) NEW_LINE second_half = self . reverse ( second_half ) NEW_LINE if ( midnode != None ) : NEW_LINE INDENT prev_of_slow_ptr . next = midnode NEW_LINE midnode . next = second_half NEW_LINE DEDENT else : NEW_LINE INDENT prev_of_slow_ptr . next = second_half NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT def reverse ( self , second_half ) : NEW_LINE INDENT prev = None NEW_LINE current = second_half NEW_LINE next = None NEW_LINE while current != None : NEW_LINE INDENT next = current . next NEW_LINE current . next = prev NEW_LINE prev = current NEW_LINE current = next NEW_LINE DEDENT second_half = prev NEW_LINE return second_half NEW_LINE DEDENT def compareLists ( self , head1 , head2 ) : NEW_LINE INDENT temp1 = head1 NEW_LINE temp2 = head2 NEW_LINE while ( temp1 and temp2 ) : NEW_LINE INDENT if ( temp1 . data == temp2 . data ) : NEW_LINE INDENT temp1 = temp1 . next NEW_LINE temp2 = temp2 . next NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if ( temp1 == None and temp2 == None ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT def push ( self , new_data ) : NEW_LINE INDENT new_node = Node ( new_data ) NEW_LINE new_node . next = self . head NEW_LINE self . head = new_node NEW_LINE DEDENT def printList ( self ) : NEW_LINE INDENT temp = self . head NEW_LINE while ( temp ) : NEW_LINE INDENT print ( temp . data , end = " - > " ) NEW_LINE temp = temp . next NEW_LINE DEDENT print ( " NULL " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT l = LinkedList ( ) NEW_LINE s = [ ' a ' , ' b ' , ' a ' , ' c ' , ' a ' , ' b ' , ' a ' ] NEW_LINE for i in range ( 7 ) : NEW_LINE INDENT l . push ( s [ i ] ) NEW_LINE l . printList ( ) NEW_LINE if ( l . isPalindrome ( l . head ) != False ) : NEW_LINE INDENT print ( " Is Palindrome " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not Palindrome " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT