链表中的最长回文 C++

Question

我想找出链表中是否存在回文，并打印该值。但问题是我正在使用长 int 值并希望在节点内找到回文甚至跨越节点。
IE 给定列表：123->32166->78->1222
最长的佩林应该是：123321
我已经尝试了很多东西，但我似乎无法理解如何去做。如果您不显示任何代码也没关系，但我很想听听任何解决此问题的想法。
我有一些想法： - 将节点放在一个数组中并尝试在其中找到一个 palin（虽然使用大量内存）
-反转列表并进行比较，但存在每个节点中具有不同大小的整数值的问题也就是说，将 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

在使用 LinkedList 和节点时，这是我能找到的最接近的。这个程序returns求整数串中最长回文的长度，因此如果长度至少为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; 
}

Answer 2

声明一个字符串s。遍历 linked 列表，在每个节点处，将那里的数字转换为字符串并将其附加到 s。遍历完成后，可以使用thisO(n)算法找到s.

的最长回文子串

编辑：但请注意，您将获得的答案可能从 linked 列表中的数字中间开始。例如，如果您的 linked 列表是 2->36->661 那么它会给您 666 作为答案。如果您希望回文从 linked 列表中某个数字的开头开始，您必须在单独的列表中跟踪字符串中每个数字开头的索引并使用该列表对于 link.

中给出的算法

链表中的最长回文 C++

Longest Palindrome in a Linked List C++

c++

linked-list

palindrome

nodes

data-structures