234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up: Could you do it in O(n) time and O(1) space?

bool isPalindrome(ListNode* head) { // time: O(n); space: O(1)
    if (!head || !head->next) return true;
    ListNode *slow = head, *fast = head;
    // Use slow and fast pointers to find the middle node
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // Reverse the second half
    ListNode *pre = head, *last = slow->next;
    while (last->next) {
        ListNode *nex = last->next;
        last->next = nex->next;
        nex->next = slow->next;
        slow->next = nex;
    }
    // Compare
    while (slow->next) {
        slow = slow->next;
        if (pre->val != slow->val) return false;
        pre = pre->next;
    }
    return true;
}