Interview question 02.06 Palindrome linked list

Write a function , Check whether the input list is palindromic .

Example 1：

 Input ： 1->2
 Output ： false 

Example 2：

 Input ： 1->2->2->1
 Output ： true 

Advanced ：

 Can you use  O(n)  Time complexity and  O(1)  Space complexity to solve this problem ？

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:

    ListNode *head2;
    bool f(ListNode*p){
    
        if(p==NULL){
    
            return true;
        }
        if(f(p->next)==false){
    
            return false;
        }
        if(p->val!=head2->val)return false;

        head2=head2->next;

        return true;
    }

    bool isPalindrome(ListNode* head) {
    
        head2=head;
        return f(head);


    }
};

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    // Reverse a linked list 
    ListNode* reverseList(ListNode* head) {
    
        
        if(head==NULL||head->next==NULL){
    
            return head;
        }
        ListNode* p=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return p;
    }

    bool isPalindrome(ListNode* head) {
    
        ListNode *node1=new ListNode(0,head);
        ListNode *node2=new ListNode(0,head);
        while(node2->next){
    
            node1=node1->next;
         // cout<<node1->val<<" ";
            node2=node2->next;
            if(node2->next){
    
                node2=node2->next;
            }
            else{
    
                break;
            }
        }
        node1=reverseList(node1->next);
        node2=head;
       // cout<<endl<<node1->val<<" "<<node2->val<<endl;
        while(node1){
    
            if(node1->val!=node2->val){
    
                return false;
            }
            node1=node1->next;
            node2=node2->next;
        }
        return true;


    }
};