O(n) 时间复杂度和 O(1) 空间复杂度

思路：用双指针

1、遍历链表长度 2、取中间值 3、然后把中间有右边后面的所有结点进行反转 4、反转完中间位置的右边所有链表之后，用双指针分别头尾向中间走，如果不是回文直接false结束 5、最后将链表恢复原状

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n = 0;  
        for (auto p = head; p; p = p->next) n ++ ;  //遍历链表长度
        if (n <= 1) return true;  // 长度小于或等于1肯定是回文
        int half = n / 2;  // 取链表长度一半
        auto a = head;  
        for (int i = 0; i < n - half; i ++ ) a = a->next;  // 走到中间结点位置
        auto b = a->next;  // 先存下 中间结点的next指针
        for (int i = 0; i < half - 1; i ++ ) {  // 将中间的右边链表反转
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }

        
        auto p = head, q = a;  // 存下头和尾指针
        bool success = true;  // 定义布尔值

        for (int i = 0; i < half; i ++ ) {  // 反转完中间位置的右边所有链表之后，用双指针分别头尾向中间走
            if (p->val != q->val) {  // 如果不是回文直接false结束
                success = false;
                break;
            }
            p = p->next;
            q = q->next;
        }
        auto tail = a;
        b = a->next;

        // 最后将链表恢复原状
        for (int i = 0; i < half - 1; i ++ ) {
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        tail->next  = NULL;
        return success;
    }
};