O(n) and O(1)space C++


  • 3
    W
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(head == nullptr || head->next == nullptr)
            return true;
            ListNode* slow = head;
            ListNode* fast = head->next;
            while(fast != nullptr && fast->next != nullptr){
                slow = slow->next;
                fast = fast->next->next;
            }
            ListNode* second = reverse(slow->next);
            if(fast == nullptr) slow = nullptr;
            else slow->next = nullptr;
            ListNode* first = head;
            while(first != nullptr && second != nullptr){
                if(first->val != second->val)
                return false;
                first = first->next;
                second = second->next;
            } 
            return true;
        }
        ListNode* reverse(ListNode* root){
            if(root == nullptr||root->next == nullptr) return root;
            ListNode* prev = nullptr;
            ListNode* cur = root;
            ListNode* nxt;
            while(cur){
                nxt = cur->next;
                cur->next = prev;
                prev = cur;
                cur = nxt;
            }
            return prev;
        }
    };

  • 2
    R

    I think it's better to recover the list in the end.

    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL) return true;
        ListNode* slow= head, *fast = head;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        reverse(slow);
        ListNode* cur2 = slow->next, *cur1 = head;
        bool ret = true;
        while(cur2) {
            if (cur2->val != cur1->val) {
                ret = false;
                break;
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        reverse(slow);
        return ret;
    }
    
    void reverse(ListNode* pre) {
        if (pre == NULL || pre->next == NULL) return;
        ListNode* cur = pre->next->next, *tmp = NULL;
        pre->next->next = NULL;
        while(cur) {
            tmp = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = tmp;
        }
    }

Log in to reply
 

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