C++ recursive algorithm: time O(n) and space O(n) if considering the stack expense


  • 0
    A

    The basic idea under this algorithm is easy to understand. Take the following linked list of length 5 as an example: 1->2->3->2->1, its evident that isPalindrome(1->2->3->2->1) = isPalindrome(2->3->2) && (1 == 1). For reducing the times of retrieving the linked list, the original interface is modified a little to return an additional output through the third parameter, the modified interface is like: bool isPalindrome(ListNode* head, int n, ListNode** outTail) where the second parameter n indicates the length of the linked list to be retried.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            ListNode* node = head;
            int len = 0;
            while(node)
            {
                ++len;
                node = node->next;
            }
            
            ListNode* subTail = NULL;
            return isPalindrome(head, len, &subTail);
        }
        
        
    private:
        bool isPalindrome(ListNode* head, int n, ListNode** outTail)
        {
            if(0==n)
            {
                *outTail = NULL;
                return true;
            }
            if(1==n)
            {
                *outTail = head;
                return true;
            }
            if(2==n)
            {
                *outTail = head->next;
                if(head->val == head->next->val)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            
            ListNode* subTail = NULL;
            bool res = isPalindrome(head->next,n-2, &subTail);
            *outTail = subTail->next;
            return res && (head->val == subTail->next->val);
        }
    };

Log in to reply
 

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