my O(n) time & O(1) space without reverse accept solution


  • 1
    A
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(!head) return true;
            ListNode* slow = head, *fast = head;
    // count means how many nodes of half the string
            int count = 0;
    // find the medium node
            while(fast->next){
                count++;
                fast = fast->next;
                if(fast->next){
                    fast = fast->next;
                    slow = slow->next;
                }
            }
    //     another head
            ListNode* head_2 = slow->next;
            int hash_1 = 0, hash_2 = 0;
            
    //     using hash, here choose power of 3 ,for test case like [-1, 1], power 2 is useless. I think there must be a better hash 
    
            for(int i = 1; head_2 != NULL;head = head->next, head_2 = head_2->next){
                hash_1 = (hash_1 + (i++) * (head->val * head->val * head->val) ) % 997;
                hash_2 = (hash_2 + (count--) * (head_2->val * head_2->val * head_2->val)) % 997;
            }
            return hash_1 == hash_2;
        }
    };
    

  • 0
    P
    This post is deleted!

Log in to reply
 

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