Longest Palindrome in a Linked List C++

Question

I want to find out if a palindrome exists in a linked list, and print the value. but the thing is I'm using long int values and want to find the palindrome within the node or even spanning the nodes.
i.e given list: 123->32166->78->1222
longest palin should be: 123321
I have tried so many things but I can't seem to understand how to do it. It's ok if you don't show any code but i would love to hear any ideas to solve this.
some ideas i had: -put the nodes in an array and try and find a palin in there (uses a lot of memory though)
-reverse the list and compare but there's the issue of having different sized integer values in each node i.e it wouldn't be wise to compare 78 with 32166 it would never be true
-create two pointers at tail and head and move one by one if both values are true but this also has many issues.

some code:

    int palindrome()
    {
        // node *prev,*cur,*next;
        // cur=head;
        // prev=next=NULL;
        list obj1;
        node *s,*e;
        s=obj1.head;
        e=head;
        while(s && e)
        {
             while(s->data==e->data)
             {
                  e=e->next;
                  s=s->next;
                  cout<<"\n\n\n"<<e->data<<s->data;     
             }
             if(s->data!=e->data)
             {
                  e=e->next;
             }
        }

    }

Answer 1

Declare a string s. Traverse the linked list and while at each node, convert the number there to string and append it to s. Once the traversal is done, you can use this O(n) algorithm to find the longest palindromic substring of s.

Edit: But note that the answer you'll get might be starting from the middle of a number in the linked list. For example, if your linked list is 2->36->661 then it'll give you 666 as the answer. If you want the palindrome to start at the beginning of some number in the linked list, you'll have to keep track of the index of the beginning of each numbers in the string in a separate list and use that list for the algorithm given in the link.

Answer 2

When it comes to using a LinkedList and nodes, this was the closest I was able to find. This program returns the length of the longest palindrome out of the string of integers, therefore if the length is at least 2, there does exist a palindrome. As for printing the value of the palindrome, you could simply tweak the program to, more or less, what lucieon explains.

#include <bits/stdc++.h> 
using namespace std; 

// Structure of the linked list 
struct Node 
{ 
    int data; 
    struct Node* next; 
}; 

// Function for counting the common elements 
int countCommon(Node *a, Node *b) 
{ 
    int count = 0; 
    // Loop to count common in the list starting from node a and b 
    for (; a && b; a = a->next, b = b->next) 
    {
        // increment the count for same values 
        if (a->data == b->data) 
            ++count; 
        else
            break; 
    }         
    return count; 
} 

// Returns length of the longest palindrome 
// Sublist in given list 
int maxPalindrome(Node *head) 
{ 
    int result = 0; 
    Node *prev = NULL, *curr = head;  
    // Loop until the end of the linked list 
    while (curr) 
    { 
        // The sublist from head to current reversed. 
        Node *next = curr->next; 
        curr->next = prev;  
        // Check for odd length palindrome by finding longest common list elements, beginning from prev and from next (We exclude curr) 
        result = max(result, 2*countCommon(prev, next)+1); 
        // Check for even length palindrome by finding longest common list elements, beginning from curr and from next 
        result = max(result, 2*countCommon(curr, next)); 
        // Update prev and curr for next iteration 
        prev = curr; 
        curr = next; 
    } 
    return result; 
} 

// Utility function to create a new list node 
Node *newNode(int key) 
{ 
    Node *temp = new Node; 
    temp->data = key; 
    temp->next = NULL; 
    return temp; 
} 

/* Drier program to test above functions*/
int main() 
{ 
    /* Let us create a linked lists to test the functions 
    Created list is a: 2->4->3->4->2->15 */
    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; 
}