Length of longest palindrome list in a linked list using O ( 1 ) extra space | Linked List node ; function for counting the common elements ; loop to count coomon in the list starting from node a and b ; increment the count for same values ; Returns length of the longest palindrome sublist in given list ; loop till the end of the linked list ; The sublist from head to current reversed . ; check for odd length palindrome by finding longest common list elements beginning from prev and from next ( We exclude curr ) ; check for even length palindrome by finding longest common list elements beginning from curr and from next ; update prev and curr for next iteration ; Utility function to create a new list node ; Let us create a linked lists to test the functions Created list is a : 2 -> 4 -> 3 -> 4 -> 2 -> 15
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 countCommon ( a , b ) : NEW_LINE INDENT count = 0 NEW_LINE while ( a != None and b != None ) : NEW_LINE INDENT if ( a . data == b . data ) : NEW_LINE INDENT count = count + 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT a = a . next NEW_LINE b = b . next NEW_LINE DEDENT return count NEW_LINE DEDENT def maxPalindrome ( head ) : NEW_LINE INDENT result = 0 NEW_LINE prev = None NEW_LINE curr = head NEW_LINE while ( curr != None ) : NEW_LINE INDENT next = curr . next NEW_LINE curr . next = prev NEW_LINE result = max ( result , 2 * countCommon ( prev , next ) + 1 ) NEW_LINE result = max ( result , 2 * countCommon ( curr , next ) ) NEW_LINE prev = curr NEW_LINE curr = next NEW_LINE DEDENT return result 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 ( 2 ) NEW_LINE head . next = newNode ( 4 ) NEW_LINE head . next . next = newNode ( 3 ) NEW_LINE head . next . next . next = newNode ( 4 ) NEW_LINE head . next . next . next . next = newNode ( 2 ) NEW_LINE head . next . next . next . next . next = newNode ( 15 ) NEW_LINE print ( maxPalindrome ( head ) ) NEW_LINE