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?
//234

#include<iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* createLinkedList(int arr[], int n){

    if( n == 0 )
        return NULL;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for( int i = 1 ; i < n ; i ++ ){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL ||  head->next ==NULL){
            return true;
        }
        ListNode* slow=head;
        ListNode* fast=head;
//find mid node,fast->next,fast->next->next 
        while(fast->next !=NULL && fast->next->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }

        ListNode* mid=slow->next;
        

        //reverse,mid point to NULL
        ListNode* pre=mid;
        ListNode* cur=mid->next;
        pre->next=NULL;
        while(cur != NULL){
            ListNode* next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }

        //compare,odd last all point to mid;
//even point to mid,mid+1
        ListNode* left=head;
        ListNode* right=pre;
        while(left!=NULL && right!=NULL){
            if(left->val!=right->val){
                return false;
            } else{
                left=left->next;
                right=right->next;

            }
        }
        return true;
    }
};

int main(){
    int arr[] = {1,0};
    int n = sizeof(arr)/sizeof(int);
    ListNode* head=createLinkedList(arr,n);
    cout<<Solution().isPalindrome(head)<<endl;
    return 0;
}