Clean O(n) time and O(1) space C++ solution


  • 1
    C
    ListNode *reverse(ListNode *head) {
        ListNode *prev = nullptr;
        while (head != nullptr) {
            ListNode *next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
    bool isPalindrome(ListNode *head) {
        ListNode *tail = head, *mid = head;
        while ((tail != nullptr) && (tail->next != nullptr)) {
            tail = tail->next->next;
            mid = mid->next;
        }
        tail = reverse(mid);
        while (head != mid) {
            if (head->val != tail->val) {
                return false;
            }
            head = head->next;
            tail = tail->next;
        }
        return true;
    }

Log in to reply
 

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