12ms C solution with O(n) time and O(1) space


  • 1
    Z

    Firstly, finding the middle node of the list.Secondly, reversing the botton half list.Finally,comparing the val.

    struct ListNode* reverseList(struct ListNode* head) {
        if(!head || !head->next)
            return head;
        struct ListNode *p,*q,*r;
        p = head;
        q = p->next;
        p->next = NULL;
        while(q->next){
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        q->next = p;
        return q;
        }
    
    bool isPalindrome(struct ListNode* head) {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        //get the middle node
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next;
            fast = fast->next;
        }
        ///reverse the bottom half list
        struct ListNode* rHead = reverseList(slow);
        while(head != NULL && rHead != NULL){
            if(head->val != rHead->val)
                return false;
            head = head->next;
            rHead = rHead->next;
        }
        return true;
    }

Log in to reply
 

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