c++ O(n) time and O(1) space solution, with comments


  • 0
    H
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(!head || !head->next) return true;
            ListNode* slow = head;
            ListNode* fast = head->next;
            bool even = true; // represent the number of nodes is even or odd
            while(fast->next) {
                even = false;
                fast = fast->next;
                if(fast->next) {
                    even = true;
                    fast = fast->next;
                    slow = slow->next;
                }
            }
            // get the right side list
            ListNode* head2;
            if(even) head2 = slow->next;
            else head2 = slow->next->next;
            
            // get the left sidt list by reversing the list from head to slow
            slow->next = NULL;
            ListNode* head1 = head;
            head = head->next;
            head1->next = NULL;
            while(head) {
                ListNode* tmp = head->next;
                head->next = head1;
                head1 = head;
                head = tmp;
            }
            
            // check Palindrome
            while(head1 && head2) {
                if(head1->val != head2->val) return false;
                head1 = head1->next;
                head2 = head2->next;
            }
            
            return true;
            
        }
    };
    

Log in to reply
 

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