用栈判断链表是否为回文串c++

用栈来判断链表是否为回文串是常见的算法问题，通常会先将链表转换成数组或者双向链表，然后利用栈的特性来实现。以下是使用栈的C++方法：

1. 遍历链表：首先，我们需要创建两个指针，一个正向遍历链表（`curr`），另一个反向遍历链表（`reverseCurr`）。初始时，反向指针设为链表的尾部。

2. 双向插入栈：当正向指针不为空时，将正向指针的节点值压入栈，同时移动正向和反向指针。这样可以保证栈顶元素始终包含链表中对应位置的节点。

3. 对比栈顶：当正向指针和反向指针相遇（或其中之一到达链表头）时，如果栈顶元素（正向节点）等于当前反向节点，继续比较下一个节点。如果所有节点都满足这个条件，链表就是回文的；否则不是。

4. 使用栈：C++中，可以使用`std::stack<int>`数据结构来保存节点值，`push()`用于入栈，`top()`获取栈顶元素，`pop()`移除栈顶元素。

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

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

bool isPalindrome(ListNode* head) {
    stack<int> s;
    ListNode* curr = head, *reverseCurr = new ListNode(0);
    reverseCurr->next = head;
    while (curr != nullptr && reverseCurr->next != nullptr) {
        s.push(curr->val);
        reverseCurr = reverseCurr->next;
        curr = curr->next;
    }

    while (reverseCurr->next != nullptr) {
        reverseCurr = reverseCurr->next;
    }

    while (!s.empty()) {
        if (s.top() != curr->val) {
            return false;
        }
        s.pop();
        curr = curr->next;
    }

    return true;
}

int main() {
    // 测试代码省略
    ListNode* list = ...; // 创建链表
    if (isPalindrome(list)) {
        cout << "The linked list is a palindrome." << endl;
    } else {
        cout << "The linked list is not a palindrome." << endl;
    }
    return 0;
}