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

  • 1

    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;
            slow = slow->next;
            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.