Recursive C++ solution with O(n) time, O(1) space


  • 0
    A
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            return isPalindrome(head, head);
        }
        bool isPalindrome(ListNode* head, ListNode* &t) {   // reference of pointer
            if(head == NULL)
                return true;
            if(isPalindrome(head->next, t) && (head->val == t->val))
            {
                t = t->next;
                return true;
            }
            else 
                return false;
            
        }
    };
    
    class Solution {
    public:
        ListNode *t;     // member
        bool isPalindrome(ListNode* head) {
            t = head; 
            return helper(head);
        }
        bool helper(ListNode* head) {
            if(head == NULL)
                return true;
            if(helper(head->next) && (head->val == t->val))
            {
                t = t->next;
                return true;
            }
            else 
                return false;
            
        }
    };

  • 0
    P

    recursive code uses stack space, so it's not 0(1) space!


Log in to reply
 

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