Length of longest palindrome list in a linked list using O ( 1 ) extra space | structure of the linked list ; 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 { constructor ( ) { this . data = 0 ; this . next = null ; } } function countCommon ( a , b ) { var count = 0 ; for ( ; a != null && b != null ; a = a . next , b = b . next ) if ( a . data == b . data ) ++ count ; else break ; return count ; } function maxPalindrome ( head ) { var result = 0 ; var prev = null , curr = head ; while ( curr != null ) { var next = curr . next ; curr . next = prev ; result = Math . max ( result , 2 * countCommon ( prev , next ) + 1 ) ; result = Math . max ( result , 2 * countCommon ( curr , next ) ) ; prev = curr ; curr = next ; } return result ; } function newNode ( key ) { var temp = new Node ( ) ; temp . data = key ; temp . next = null ; return temp ; } var head = newNode ( 2 ) ; head . next = newNode ( 4 ) ; head . next . next = newNode ( 3 ) ; head . next . next . next = newNode ( 4 ) ; head . next . next . next . next = newNode ( 2 ) ; head . next . next . next . next . next = newNode ( 15 ) ; document . write ( maxPalindrome ( head ) ) ;