O(1) space and O(n) time C++ solution


  • 2
    O

    Idea: reverse the latter half part; compare with the former half part; reverse the latter half part.

    Because the test case must delete the linked-list in C++, so the third step (recover the latter half part) is essential. Otherwise, it will form a cycle in the linked-list and result a "Time limit exceeded".

    bool isPalindrome(ListNode* head) {
        size_t n = 0;
        ListNode * p = head;
        while(p) p = p->next, ++n;
        if (n == 1 || n == 0) return true;
        if (n == 2) return head->val == head->next->val;
        
        ListNode * r = head;
        for(int i = 0; i < n/2; ++i) r = r->next;
        if (n % 2 != 0) r = r->next;
        
        //reverse the latter half part
        p = r->next;
        while(p)
        {
            ListNode * tmp = p->next;
            p->next = r;
            r = p;
            p = tmp;
        }
        
        int index = 0;
        p = head;
        ListNode * e = r;
        for(index = 0; index < n/2 && p->val == r->val; ++index)
        {
            p = p->next;
            r = r->next;
        }
        bool res = index == n/2;
        
        //reverse the latter half part again
        p = e->next;
        e->next = nullptr;
        for(index = 0; index < n / 2 - 1; ++index)
        {
            ListNode * tmp = p->next;
            p->next = e;
            e = p;
            p = tmp;
        }
        return res;
    }

  • 0
    R

    I didn't do the step 3 reverse the latter half but it still AC. The difference with your code is that I assign NULL to the next of the last node of the reversed latter half.

    bool isPalindrome(ListNode* head) {
        if(!head || !head->next){
            return true;
        }
        int count = 0;
        ListNode* temp = head;
        while(temp){
            temp = temp->next;
            count++;
        }
        ListNode *l2;
        temp = head;
        int i=1;
        while(i<count/2){
            temp = temp->next;
            i++;
        }
        if(count%2==0){
            l2 = temp->next;
        }
        else{
            l2 = temp->next->next;
        }
        ListNode* newnext = NULL;//the first new next is NULL;
        while(l2->next){
            temp = l2->next;
            l2->next = newnext;
            newnext = l2;
            l2 = temp;
        }
        l2->next = newnext;
        while(l2){
            if(l2->val != head->val){
                return false;
            }
            l2 = l2->next;
            head = head->next;
        }
        return true;
    }

Log in to reply
 

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