C++ recursive sol (O(n) time, O(n) space)


  • 0
    M

    Since recursion is used this solution does not satisfy the requirement of O(1) space. Instead, it uses O(n) space. (For O(1) space solution one needs to reverse the "right-half" of the input list "in-place".)

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            ListNode* slow = head, * fast = head;
            while(fast != nullptr && fast->next != nullptr) {
                fast = fast->next->next;
                slow = slow->next;
            }
            if(fast != nullptr) slow = slow->next;
            
            return isPalin(head, slow);
        }
        
        bool isPalin(ListNode*& head1, ListNode* head2) {
            if(head2 == nullptr) return true;
            bool result = isPalin(head1, head2->next);
            if(!result || head1->val != head2->val) return false;
            head1 = head1->next;
            return true;
        }
    };

Log in to reply
 

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