My C++ O(N) time, O(1) space code (reverse the first half of the list, compare, and recover the first half)


  • 0
    D

    The idea is

    1. find the length of the list and then reverse the first half of
      the list,
    2. compare the reversed first half with the second half
      to get the result,
    3. reverse the first half again to recover the
      list

    So the algorithm has O(N) time complexity

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            int i, len =0;
            ListNode *prev, *cur = head, *suc, *sHead;
            bool res = true;
    
            // calculate the length of the list
            while(cur) 
            {
                ++len; 
                cur = cur->next;
                
            }
            
            if(len<=1) return true;
            else if(2==len) return (head->val == head->next->val);
            else
            {
                //reverse the first half of the list
                for(i = 0, cur = head, prev = nullptr; i<len/2; ++i)
                {
                    suc = cur->next;
                    cur->next = prev;
                    prev = cur;
                    cur = suc;
                }
                
                head  = prev; // head now points to the head of the reversed first half list
                sHead = len%2 ? suc->next:suc; // sHead is the head of the second half list, for odd length, skip the middle node
                
                // compare
                while(sHead && (sHead->val == head->val))
                {
                    sHead = sHead->next;
                    head  = head->next;
                }
                res = (nullptr == sHead); // update the return value
                
                //reverse the first half of the list again;
                cur  =prev;
                prev = suc;
                for(auto i = 0; i<len/2 ; ++i)
                {
                    suc = cur->next;
                    cur->next = prev;
                    prev = cur;
                    cur = suc;
                }
                
                return res;
            }
        }
    };

Log in to reply
 

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