You should not change the original structure of LinkedList. So use Recurssion


  • 0
    S
    class Solution {
    public:
        bool isPalindrome_internal(ListNode *p, ListNode **q, int len) {
            
            //base case
            if (p->next == *q || ((len % 2) && p->next->next == *q)) {
                if (p->val == (*q)->val) {
                    *q = (*q)->next; //if base case is palindrome, adjust q to q->next, p will become p->prev when sub call returned
                    return true;
                }
                return false;
            }
            // recursively test if sub link is palindrome
            bool sub_valid =  isPalindrome_internal(p->next, q, len);
            if (!sub_valid) return false;
            
            //sub link is valid, added front and end are equal
            if (p->val == (*q)->val) {
                *q = (*q)->next;
                return true;
            }
            return false;
        }
        
        bool isPalindrome(ListNode* head) {
            if (!head || !head->next) return true;
            
            //count the length of linked-list
            ListNode *p = head;
            int len = 1;
            while (p->next) {
                len++;
                p = p->next;
            }
            if (len <= 1) return true;
            
            //initial q to point to the mid node+1 eg: 1 2 1 q=1. 1 2 2 1 q = 2. 1 2 3 4 1 q = 4.
            ListNode *q = head;
            for (int i = 0; i < (len+1)/2; i++) q = q->next;
            
            return isPalindrome_internal(head, &q, len);
        }
    };

  • 0
    C

    but recursion needs o(n) space


Log in to reply
 

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