Simple C++ Solution with O(1) space and O(n) time


#1
void reverseList(ListNode* &A){
    ListNode* cur=A;
    ListNode* prev=NULL;
    ListNode* nex=NULL;
    while(cur){
        nex=cur->next; 
        cur->next=prev; 
        prev=cur; 
        cur=nex;    
    }
    A=prev;
} 

int Solution::lPalin(ListNode* A) {
    ListNode*tmp=A;
    int len=0;
    while(tmp){
        len++;
        tmp=tmp->next;
    }
    if(len==1) return 1;
    len=(len-1)/2;
    tmp=A;
    // finding mid node
    for(int i=0;i<=len;i++)
        tmp=tmp->next;
    
    reverseList(tmp);
    
    // comparing values from mid node and head node
    while(A and tmp){
        if(A->val!=tmp->val) return 0;
        A=A->next;
        tmp=tmp->next;
    }
    return 1;
}