C++数据结构与算法之判断一个链表是否为回文结构的方法

当我们遇到判断一个链表是否为回文结构的问题时，可以考虑使用如下的方法：

1. 遍历链表，将链表节点的值存储到一个数组或者栈中。
2. 遍历链表，将链表节点的值与前面存储的值进行比较，如果全部相同，则证明链表为回文结构。

下面是详细的代码实现和示例说明：

实现

首先，我们需要定义一个链表节点的结构体，包括节点值和指向下一个节点的指针：

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

然后，我们可以定义一个函数 isPalindrome(ListNode* head)，该函数用于判断一个链表是否为回文结构。

在该函数中，我们可以先遍历链表，将链表节点的值存储到一个数组或者栈中。接着，我们再次遍历链表，将链表节点的值与前面存储的值进行比较，如果全部相同，则证明链表为回文结构。

下面是完整代码实现：

bool isPalindrome(ListNode* head) {
    vector<int> nums; // 存储链表节点的值
    ListNode* cur = head;
    while (cur != NULL) {
        nums.push_back(cur->val);
        cur = cur->next;
    }
    int n = nums.size();
    for (int i = 0; i < n / 2; i++) {
        if (nums[i] != nums[n - i - 1]) {
            return false;
        }
    }
    return true;
}

示例说明

下面我们来分别看两个示例，帮助理解上面的代码实现。

示例一

链表为 1 -> 2 -> 2 -> 1，这是一个回文结构，应该返回 true。

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(1);
bool res = isPalindrome(head); // true

示例二

链表为 1 -> 2 -> 3 -> 2 -> 1，这是一个回文结构，应该返回 true。

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 res = isPalindrome(head); // true

感谢阅读，希望对你有所帮助！