share my c++ solution O(n) time and O(1) space .


  • 1
    R

    find the middle and reverse the first half in the same pass .now compare the reversed first half with the second half

    bool isPalindrome(ListNode* head) {

        ListNode *slow = head , *fast=head ,*rev=NULL, *temp;
        
        while(fast && fast->next){
            fast = fast->next->next;
            temp = rev;
            rev = slow;
            slow = slow->next;
            rev->next = temp;
        }
        
        if(fast){
            slow = slow->next;
        }
        
        while(slow){
            if(slow->val != rev->val)  return false;
            slow = slow->next;
            rev = rev->next;
        }
        
        return rev == NULL;
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.