C++判断链表是否为回文链表

要判断一个链表是否为回文链表，可以使用双指针和栈的方法。以下是使用C++实现的一个示例：

#include <iostream>
#include <stack>
using namespace std;

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

bool isPalindrome(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        // 链表为空或只有一个节点，视为回文链表
        return true;
    }

    ListNode* slow = head;  // 慢指针
    ListNode* fast = head;  // 快指针
    stack<int> st;  // 用于存储前半部分节点的值

    // 将慢指针移到链表的中间位置，并将前半部分节点的值存入栈中
    while (fast != nullptr && fast->next != nullptr) {
        st.push(slow->val);
        slow = slow->next;
        fast = fast->next->next;
    }

    // 链表长度为奇数，跳过中间节点
    if (fast != nullptr) {
        slow = slow->next;
    }

    // 逐个比较后半部分节点的值与栈中的值
    while (slow != nullptr) {
        if (slow->val != st.top()) {
            return false;
        }
        st.pop();
        slow = slow->next;
    }

    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 palindrome = isPalindrome(head);
    if (palindrome) {
        cout << "链表是回文链表" << endl;
    } else {
        cout << "链表不是回文链表" << endl;
    }

    // 释放链表内存
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* temp = curr;
        curr = curr->next;
        delete temp;
    }

    return 0;
}

在上述代码中，我们使用了两个指针，一个慢指针和一个快指针。快指针每次移动两个节点，慢指针每次移动一个节点。同时，我们使用一个栈来存储前半部分节点的值。当快指针到达链表末尾时，慢指针指向链表中间位置。然后，我们将慢指针后面的节点值与栈中的值逐个进行比较，如果不相等，则链表不是回文链表。

注意，在实际应用中，我们还需要考虑链表为空或只有一个节点的情况。这种情况下，我们可以视链表为回文链表。