Hash+Reverse+O(1) Space cheating solution for C++

  • 0

    This method tries to extract direction-dependent features in both directions and check if they are equal.
    I design a hash function to combine the elements into a feature variable(code[i]) in particular order thus the feature variable can be a summarize of all elements with direction feature.
    It is of course a cheating solution coz there is no one-to-one mapping for vector to integer.

    class Solution {
        bool isPalindrome(ListNode* head) {
            if(head == NULL || head->next == NULL)return true;
            int len = 0;
            // two hash mask numbers
            int m1 = 0x13349057;
            int m2 = 0x34129522;
            // used to store hash codes
            int code[] = {0,0,0,0};
            // get the hash codes from v[0] to v[n-1]
            ListNode* ptr = head;
                code[0] = dohash(code[0], ptr->val, m1);
                code[1] = dohash(code[1], ptr->val, m2);
                if(ptr->next == NULL)break;
                ptr = ptr->next;
            //ptr->next = head;
            ptr = head;
            ListNode* pre = NULL;
            ListNode* pro = NULL;
            // reverse the whole linklist
                pro = ptr->next;
                ptr->next = pre;
                pre = ptr;
                if(pro == NULL)break;
                ptr = pro;
            // get the hash codes from v[n-1] to v[0]
                code[2] = dohash(code[2], ptr->val, m1);
                code[3] = dohash(code[3], ptr->val, m2);
                if(ptr->next == NULL)break;
                ptr = ptr->next;
            // double check if the hash codes equal
            return code[0] == code[2] && code[1] == code[3];
        int dohash(int a, int b, int mask){
            int tmp = b*b*b + 3;
            return (a + tmp) ^ mask;

Log in to reply

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