19ms O(n) time, O(1)* space C++ solution (not reversing list)


  • 0
    S

    Basic idea.

    Getting O(n) in time is trivial. The problem with space complexity of this problem is that when checking the i-th list, we need to compare with the (N-i)-th list, which can't be naively accessed in O(1) time. Inspired by the solution for Implement Queue using stacks , we can achieve O(1) space (not including function stack) in a similar fashion.

    The main point is, while traversing to the (N-i)-th list, we also check the lists along the path.

    Implementation detail

    We need to return have two things from the recursion:

    • pointer to (N-i)-th list
    • whether the sublists in between form a palindrome.

    Instead of creating a new class, I simply used the given ListNode structure, where:

    • val is value of (N-i)-th list, but if the sublists in between is not palindrome, this value will be set to val[i] + 1 so that comparing val[i] and val is never true;
    • next pointer to (N-i)-th list

    We only need to create one ListNode which will be propagated through the recursion. Hence the extra space is O(1). Of course, if counting the space used for recursion stack, it's still O(n).

    Code

    Below is my 19ms accepted answer.

    class Solution {
    private:
        ListNode* helper(ListNode* head,int n) 
            /*head: pointer at i-th list
              n: lists length
              node->val: val[i+n] or val[i]+1
              node->next: pointer to (i+n)-th list
            */
            if (n==1) {
                ListNode* node = new ListNode(head->val);
                node->next=head;
                return node;
            }
            if (n==2) {
                ListNode* node = new ListNode(head->next->val);
                node->next = head->next;
                return node;
            }
            //recursion on (i+1) and (n-i-1)
            ListNode* node = helper(head->next, i-2);
            node->next = node->next->next; // points to (n-i)th list
            //only return val[n-i] if sublists form palindrome.
            if (head->next->val != node->val) node->val = head->val+1;
            //otherwise return val[i]+1 for false comparison result
            else node->val = node->next->val;
            return node;
            
        }
    public:
        bool isPalindrome(ListNode* head) {
            int n=0;
            ListNode* node=head;
            while(node) {
                n++;
                node=node->next;
            }
            if(!n) return true;
            node = helper(head,n);
            int val = node->val;
            delete node;
            return head->val == val;
        }
    };
    

Log in to reply
 

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