判断回文链表 c++

判断回文链表是一个常见的问题，可以通过以下步骤来实现：

1. 遍历链表，将链表的值存储在一个数组中。
2. 使用双指针法，一个指针从数组的开头开始，另一个指针从数组的末尾开始，逐个比较两个指针指向的值是否相等。
3. 如果两个指针指向的值不相等，则链表不是回文链表；如果两个指针相遇，则链表是回文链表。

下面是C++的示例代码：

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

bool isPalindrome(ListNode* head) {
    vector<int> vals;
    ListNode* curr = head;
    while (curr != NULL) {
        vals.push_back(curr->val);
        curr = curr->next;
    }
    
    int left = 0;
    int right = vals.size() - 1;
    while (left < right) {
        if (vals[left] != vals[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

int main() {
    // 构造一个回文链表：1->2->3->2->1
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(1);
    
    bool result = isPalindrome(head);
    cout << "Is the linked list a palindrome? " << (result ? "Yes" : "No") << endl;
    
    return 0;
}