Simple C++ O(N) Time O(1) Space solution


  • 0
    C
    ListNode * reverse(ListNode* head)
    {
        if(!head || !head->next)return head;
        ListNode* lst = reverse(head->next);
        head->next->next = head;
        head->next = NULL;
        return lst;
    }
    
    bool isPalindrome(ListNode* head) {
        
        if(!head || !head->next)return true;
        if(!head->next->next)
        {
            if(head->val == head->next->val)return true;
            else return false;
        }
        ListNode *slow = head, *fast = head;
        ListNode * slow_pre = NULL;
        while(fast && fast->next)
        {
            slow_pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        if(!fast)slow = slow_pre;
        ListNode *new_lst = slow->next;
        slow->next = NULL;
        new_lst = reverse(new_lst);
        ListNode *p1 = new_lst;
        ListNode *p2 = head;
        while(p1)
        {
            if(p1->val != p2->val)return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }

Log in to reply
 

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