题解 | #判断一个链表是否为回文结构#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        if (head == NULL) return false;
        if (head->next == NULL) return true;
        if (head->next->next == NULL) return false;

        ListNode* slow = head, * fast = head;
        stack<int> sk;
        while (fast) {
            sk.push(slow->val);
            slow = slow->next;
            if (fast->next)fast = fast->next->next;
            else break;
        }
        if (fast) {
            //奇数
            sk.pop();
        }
        while (slow) {
            if (slow->val != sk.top()) return false;
            sk.pop();
            slow = slow->next;
        }
        return true;
    }
};

采用快慢指针的思路，先让慢指针走到链表中间，并用栈记录沿途的值，然后再让慢指针将链表后半部分的值与栈顶元素一一对比。