判断一个链表是否为回文结构

判断一个链表是否为回文结构

一、题目

给定一个链表的头节点 head，请判断该链表是否为回文结构。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

leetcode：https://leetcode.cn/problems/aMhZSa/

二、思路

我们可以使用栈的性质来做，将链表中的元素插入到栈中。栈有先进后出的性质，所以当把所有元素插入进去之后，从栈中依次取出来的元素顺序就是从链表的尾部向头部遍历的过程。在和原链表进行比对即可。这是第一种思路。

如上的这种思路还有可以优化的余地，我们不用插入链表中所有的元素，我们只需要插入链表中一半的元素即可。并且插入链表的后半部分。如果链表的长度是奇数，那就忽略最中间的那个元素；如果链表的长度是偶数，那就可以等分。可以使用快慢指针获取到链表的中间位置。

三、代码

#include <stack>
#include <iostream>

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

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 此算法求的 slow 为中间元素
        ListNode* fast = head, *slow = head;
        for (; fast != nullptr && fast->next != nullptr;) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 如果是 fast == nullptr 表示链表的长度为偶数，slow 位于下半部分的第一位，这种情况我们不用管
        // 如果 fast->next = nullptr 表示链表的长度为奇数，slow 位于中心元素，让他在走一步
        // 注意这里要判断 fast != nullptr
        if (fast != nullptr && fast->next == nullptr) {
            slow = slow->next;
        }
        while (slow != nullptr) {
            st_.emplace(slow->val);
            slow = slow->next;
        }
        while (!st_.empty() && head != nullptr) {
            if (st_.top() != head->val) {
                return false;
            }
            st_.pop();
            head = head->next;
        }
        if (!st_.empty()) {
            return false;
        }
        return true;
    }

private:
    std::stack<int> st_;
};

由于使用了栈，所以空间复杂度为 O(n)，时间复杂度也为 O(n)