思路

1. 借助一个数组将链表的值存入数组中，然后使用两个指针，一个指向数组头部，一个指向数组尾部，向中间逼近并比较值。
2. 快慢指针，快指针比慢指针多走一半的路程，从慢指针往后开始反转链表，依次比较链表值

步骤

1. 辅助数组法

1. 初始化数组遍历链表，将链表值存入数组中并在遍历过程中记录数组长度 len
2. 设置一个左指针=0，右指针=len-1，只要左指针小于右指针，判断指向数值是否一致，若不一致，立马返回 false
3. 若循环条件满足时没有跳出，则说明为回文结构

2.快慢指针法

1. 找中点：使用快慢指针（fast 每次走两步，slow 每次走一步），当 fast 到达末尾时，slow 刚好位于链表中间。
2. 反转后半段：将 slow 之后的链表部分进行原地反转。
3. 比较：从头节点和反转后的中间节点开始，同时向后移动比较。

反转链表法--链表相加

正确答案

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        if (head == nullptr) return false;
        std::vector<int> vals;
        ListNode* p = head;
        int len = 0;
        while (p) {
            vals.push_back(p->val);
            p = p->next;
            len++;
        }
        int left = 0, right = len - 1;
        while (left < right) {
            if (vals[left] != vals[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;

    }
};

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