Leetcode 234: palindrome linked list

Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?

这个题目是判断一个linked list是不是palindrome, 可以先找到middle node， reverse后半段的linked list，如果是palindrome那么前后两部分应该是相同的。

class Solution {
private:
    ListNode* reverse(ListNode* head) {
        //snaity checko
        if (head == NULL || head->next == NULL) return head;
        ListNode* cur = head;
        ListNode* next = cur->next;
        ListNode* nnode = reverse(next);
        next->next = cur;
        cur->next = NULL;
        return nnode;
    }
public:
    bool isPalindrome(ListNode* head) {
        //sanity cehck
        if (head == NULL) return true;
        //find mid
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* mid = slow;
        ListNode* p = reverse(mid->next);
        slow = head;
        while (p) {
            if (slow->val == p->val) {
                slow = slow->next;
                p = p->next;
            } else {
                break;
            }
        }
        if (p == NULL) return true;
        return false;
    }
};