Самый длинный палиндром в связанном списке C ++

Question

Я хочу выяснить, существует ли палиндром в связанном списке, и распечатать значение. но дело в том, что я использую длинные int значения и хочу найти палиндром внутри узла или даже охватить узлы.
то есть данный список: 123-> 32166-> 78-> 1222
самый длинный пэйлин должен быть: 123321
Я пробовал так много вещей, но не могу понять, как это сделать. Это нормально, если вы не показываете какой-либо код, но мне бы хотелось услышать любые идеи, чтобы решить эту проблему.
некоторые идеи, которые у меня были: -введите узлы в массив и попытайтесь найти там пэлин (использует многопамять)
- перевернуть список и сравнить, но есть проблема с целочисленными значениями разного размера в каждом узле, то есть было бы неразумно сравнивать 78 с 32166, это никогда не было бы верно
- создавать два указателя вхвост и голова и двигайтесь по одному, если оба значения верны, но это также имеет много проблем.

некоторый код:

    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

Объявить строку s. Пройдите по связанному списку и, находясь в каждом узле, преобразуйте число в строку и добавьте его к s. После завершения обхода вы можете использовать этот O(n) алгоритм, чтобы найти самую длинную палиндромную подстроку из s.

Редактировать: Но обратите внимание, что ответ, который вы получите, может бытьначиная с середины номера в связанном списке. Например, если у вас есть связанный список 2->36->661, он даст вам 666 в качестве ответа. Если вы хотите, чтобы палиндром начинался с начала некоторого числа в связанном списке, вам нужно будет отслеживать индекс начала каждого числа в строке в отдельном списке и использовать этот список для алгоритма, приведенного вссылка.

Answer 2

Когда дело доходит до использования LinkedList и узлов, это было самое близкое, что мне удалось найти. Эта программа возвращает длину самого длинного палиндрома из строки целых чисел, поэтому, если длина равна по крайней мере 2, существует палиндром. Что касается печати значения палиндрома, вы можете просто настроить программу, чтобы более или менее объяснить то, что объясняет lucieon.

#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; 
}