C++ 链表回文判断算法：空间复杂度 O(1) 实现

时间复杂度：O(n)，其中n为链表长度。我们对链表遍历了一次，时间复杂度为O(n)。 空间复杂度：O(1)，我们只用了常量级别的额外空间。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* pre = nullptr;
        ListNode* cur = slow->next;
        slow->next = nullptr;
        while(cur){
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        while(head && pre){
            if(head->val != pre->val) return false;
            head = head->next;
            pre = pre->next;
        }
        return true;
    }
};