Simple C Solution, O(N) Time, O(1) Space


  • 0
    F
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    bool isPalindrome(struct ListNode* head) {
        bool ret = true;
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        struct ListNode* pre = NULL;
        struct ListNode* tmp = NULL;
        
        if (!head || !head->next)
            return true;
        
        while(fast && fast->next){
            fast = fast->next->next;
            tmp = slow->next;
            slow->next = pre;
            pre = slow;
            slow = tmp;
        }
        if(fast){   //odd
            fast = slow->next;
        }
        else
            fast = slow;
        slow = pre;
        
        while(slow){
            if (slow->val != fast->val)
                return false;
            slow = slow->next;
            fast = fast->next;
        }
        
        return true;
    }
    

Log in to reply
 

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