234.回文链表 (Easy)*

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return true;
        }
        ListNode *slow = head, *fast = head;
        // 这样的条件就不用判断奇偶
        while(fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *last = slow->next, *pre = head;
        // 后半段链表反转
        slow = nullptr, fast = last;
        while(fast != nullptr) {
            ListNode *p = fast->next;
            fast->next = slow;
            slow = fast;
            fast = p;
        }
        // 反转后 slow 成为后半段链表头
        while(slow != nullptr) {
            if(slow->val != pre->val) {
                return false;
            }
            slow = slow->next;
            pre = pre->next;
        }
        return true;
    }
};