The idea is

- find the length of the list and then reverse the first half of

the list, - compare the reversed first half with the second half

to get the result, - reverse the first half again to recover the

list

So the algorithm has O(N) time complexity

```
class Solution {
public:
bool isPalindrome(ListNode* head) {
int i, len =0;
ListNode *prev, *cur = head, *suc, *sHead;
bool res = true;
// calculate the length of the list
while(cur)
{
++len;
cur = cur->next;
}
if(len<=1) return true;
else if(2==len) return (head->val == head->next->val);
else
{
//reverse the first half of the list
for(i = 0, cur = head, prev = nullptr; i<len/2; ++i)
{
suc = cur->next;
cur->next = prev;
prev = cur;
cur = suc;
}
head = prev; // head now points to the head of the reversed first half list
sHead = len%2 ? suc->next:suc; // sHead is the head of the second half list, for odd length, skip the middle node
// compare
while(sHead && (sHead->val == head->val))
{
sHead = sHead->next;
head = head->next;
}
res = (nullptr == sHead); // update the return value
//reverse the first half of the list again;
cur =prev;
prev = suc;
for(auto i = 0; i<len/2 ; ++i)
{
suc = cur->next;
cur->next = prev;
prev = cur;
cur = suc;
}
return res;
}
}
};
```