A well framed O(n) time code.


  • 0
    N
    ListNode *reverse(ListNode *curr){
        ListNode *prev = NULL;
        while(curr){
            auto temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
    
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(!head or !head->next)   return true;
            ListNode *slow = head,*fast = head;
            while(fast){
                fast = fast->next;
                if(fast){
                    fast = fast->next;
                    slow = slow->next;
                }
            }
            ListNode *rev = reverse(slow);
            int p = 0;
            while(rev and head){
                if(rev->val!=head->val){
                    p=1;
                    break;
                }
                rev = rev->next;
                head = head->next;
            }
            return p==0;
        }
    };
    

Log in to reply
 

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