C++ Easy to Understand O(n) Time, O(1) Space Solution with Explanations (by reversing half of the list)


  • 0

    The basic idea is to reverse the second half of the list and advance two pointers simultaneously to check whether the values are the same

        bool isPalindrome(ListNode* head) {
            if (!head || !head->next)  return true;
            ListNode* slow = head, *fast = head->next;
            
            //find the node just before the second half
            while (fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            
            //reverse the second half
            slow->next = reverse(slow->next);
            
            // Check palindrome
            /* E.g. After the reverse, 1-2-3-2-1 becomes
               1 - 2 - 3 - 1 - 2 
               |           |          
              fast        slow
             
              Move both pointers simultaneously, 
              and if any of the values don't match, it is not a palindrome
            */
            
            fast = head;
            slow = slow->next;
            while (fast && slow) {
                if (fast->val != slow->val)
                    return false;
                fast = fast->next;
                slow = slow->next;
            }
            
            return true;
        }
    

    The helper function Reverse Explanations

        /* helper function to reverse the second half of the list
            Explained here: https://discuss.leetcode.com/category/214/reverse-linked-list
       */
    
        ListNode* reverse(ListNode* node) {
            ListNode* prev = NULL;
            ListNode* curr = node;
            ListNode* temp;
            while(curr != NULL) {
                temp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = temp;
            }
            return prev;
        }
    

    Plus a little helper function to print the list so it's easier to tell

        void printList(ListNode* head) {
            while (head->next != NULL) {
                cout << head->val << "->";
                head = head->next;
            }
            cout << head->val;
            cout <<endl;
        }
    

Log in to reply
 

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