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

思路是遍历所有结点，构造一个数组，并反转数组，然后顺序与链表结点比较，只比较一半即可判断是否是回文结构

// 注意：快指针一次走两步，慢指针一次走一步，可以实现寻找链表的中间结点
// 空间复杂度为1的思路是通过快慢指针找到中间结点，然后将中间结点以后的结点反转，然后分别从两条链的链首开始遍历，判断相等进而判断是否是回文串
// 下边方法空间复杂度为O(n)

#include <bits/stdc++.h>
using namespace std;

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



class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        // 判断链表是否是回文结构
        // 只能使用头插法复制一份逆转后的链表，然后使用双指针法比较一半的链表？
        if (!head) return true;
        vector<int> rvec;
        ListNode *cur = head;
        while (cur) {
            rvec.push_back(cur->val);
            cur = cur->next;
        }

        reverse(rvec.begin(), rvec.end());
        cur = head;

        for (int i = 0; i < rvec.size()/2; i++, cur = cur->next) {
            if (cur->val != rvec[i]) return false;
        }

        return true;

    }
};