234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/description/
Solution 1. Use a recursive call to check the values. The call stack acts as a stack for the node values, which access the node values backwardly. At the same time, use a pointer p to access the node values forwardly. O(n) in space.
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        return check(head, p);
    }
    bool check(ListNode* node, ListNode*& p) {
        if(!node) return true;
        bool isNext = check(node->next,p) && (node->val == p->val);
        p = p->next;
        return isNext;
    }
Solution 2. O(1) space?
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        ListNode* slow = head, * fast = head, *p;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = reverseList(slow->next);
        slow->next = fast;
        p = head;
        while(fast) {
            if(p->val != fast->val) return false;
            p = p->next;
            fast = fast->next;
        }
        slow->next = reverseList(slow->next);
        return true;
    }
    ListNode* reverseList(ListNode* head){
        ListNode* hd = nullptr, * next;
        while(head) {
            next = head->next;
            head->next = hd;
            hd = head;
            head = next;
        }
        return hd;
    }