Short and Simple Recursive C++ code with explanation


  • 0
    N

    Store the reference of head in variable head1 and move head to end of the list. During unwinding phase of recursion compare the value of head and head1. If they match increment head1 else return false.
    Its not O(1) space but the the solution is pretty neat.

    bool isPalindrome(ListNode* head) {
                return isPalin(head,&head);
            }   
            bool isPalin(ListNode* head, ListNode **head1)
            {
                if(!head)   
                    return true;
                bool isp = isPalin(head->next,head1);
                if((*head1)->val==head->val)
                {
                    (*head1) = (*head1)->next;
                    return isp;
                }
                else
                    return false;
            }

Log in to reply
 

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