```
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;
}
};
```