Recursion won't be considered O(1) space, right?


  • 1
    A

    I'll post my recursion solution anyways:

    bool isPalindrome(ListNode* head) {
         
        return !head||helper(head, head);
    }
    
    bool helper(ListNode* reverse, ListNode* &normal){
        bool isP = true;
        if(reverse->next)
            isP = helper(reverse->next, normal);
    
        isP  = isP && (reverse->val == normal->val);
        normal = normal->next;
        
        return isP;
    }
    

    Use recursion to go to last one, and compare backwards.


  • 1
    Q

    Yes, recursion is actually O(n) space.


Log in to reply
 

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