Space cost from O(n) to O(1) in C, both accepted as best and well-commented


  • 0
    //AC - 12ms - using extra space to reduce complexity;
    bool isPalindrome(struct ListNode* head)
    {
        int* arr = (int*)malloc(sizeof(int));
        int size = 0;
        struct ListNode* p = head;
        while(p) //collect all values;
        {
            size++;
            arr = (int*)realloc(arr, sizeof(int)*size);
            arr[size-1] = p->val;
            p = p->next;
        }
        for(int i = 0; i < size/2; i++) //symmetric;
            if(arr[i] != arr[size-i-1])
                return false;
        return true;
    }
    

    //AC - 12ms - using slow and fast pointer to split it up;
    bool isPalindrome(struct ListNode* head)
    {
        if(!head || !head->next) return true;
        struct ListNode *slow=head, *fast=head->next->next;
        while(fast && fast->next) //split into two halves while the right part might longer by 1 if the length of the link is odd;
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        struct ListNode *cur, *pre, *next; //reverse the left linked and slow will become the head;
        cur = head->next;
        pre = head;
        pre->next = NULL;
        while(cur)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        if(fast->val != slow->val) fast = fast->next; //if the first node is unequal, move fast forward to the next;
        while(fast)
        {
            if(fast->val != slow->val)
                return false;
            fast = fast->next;
            slow = slow->next;
        }
        if(slow) return false; //fast must be null now, if slow is not then not all nodes have been compared - not symmetric;
        return true;
    }

Log in to reply
 

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