My O(n) time, O(1) space cpp code


  • 0
    C
    class Solution {
    public:
    
        void findListCenter(ListNode *head, ListNode *&center, ListNode *&last_half)
        {
            ListNode *slow = head, *fast = head;
            
            while(fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            
            if(fast) // odd
            {
                center = slow;
                last_half = slow->next;
            }
            else // even
                center = last_half = slow;
        }
        
        ListNode *ReverseList(ListNode *head)
        {
            ListNode *reversedHead = NULL;
            
            while(head)
            {
                ListNode *tmp = head->next;
                head->next = reversedHead;
                reversedHead = head;
                head = tmp;
            }
            
            return reversedHead;
        }
    
        bool isPalindrome(ListNode* head) 
        {
            if(!head || !head->next) return true; 
            
            ListNode *center, *last_half;
            findListCenter(head, center, last_half);
            
            last_half = ReverseList(last_half);
            
            // check
            for(; last_half; last_half = last_half->next, head = head->next)
                if(head->val != last_half->val)
                    return false;
            
            return true;
        }
    };

Log in to reply
 

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