O(n) time O(1) space C++ solution with in-place partial reverse


  • 0
    D

    Step 1: Using a fast pointer, find the middle of the list.

    Step 2: Reverse the second half of the list (starting at middle).

    Step 3: Compare the values in the first and second halves pairwise.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            auto front = head, middle = head, fast = head;
            while (fast) {
                fast = fast->next;
                if (fast) {
                    fast = fast->next, middle = middle->next;
                }
            }
            ListNode* prev = nullptr;
            while (middle) {
                auto temp = middle->next;
                middle->next = prev;
                prev = middle;
                middle = temp;
            }
            auto back = prev;
            while (front && back) {
                if (back->val != front->val) { return false; }
                front = front->next, back = back->next;
            }
            return true;
        }
    };

Log in to reply
 

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