Length of longest palindrome list in a linked list using O ( 1 ) extra space | C ++ program to find longest palindrome sublist in a list in O ( 1 ) time . ; 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 ; Driver program to test above functions ; Let us create a linked lists to test the functions Created list is a : 2 -> 4 -> 3 -> 4 -> 2 -> 15
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; int countCommon ( Node * a , Node * b ) { int count = 0 ; for ( ; a && b ; a = a -> next , b = b -> next ) if ( a -> data == b -> data ) ++ count ; else break ; return count ; } int maxPalindrome ( Node * head ) { int result = 0 ; Node * prev = NULL , * curr = head ; while ( curr ) { Node * next = curr -> next ; curr -> next = prev ; result = max ( result , 2 * countCommon ( prev , next ) + 1 ) ; result = max ( result , 2 * countCommon ( curr , next ) ) ; prev = curr ; curr = next ; } return result ; } Node * newNode ( int key ) { Node * temp = new Node ; temp -> data = key ; temp -> next = NULL ; return temp ; } int main ( ) { Node * 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 ) ; cout << maxPalindrome ( head ) << endl ; return 0 ; }