```
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(NULL == head)
{
return true;
}
ListNode* node = head;
int len = 0;
while(node)
{
++len;
node = node->next;
}
ListNode* leftHead = NULL;
ListNode* rightHead = NULL;
split(head, len, leftHead, rightHead);
return isPalindrome(leftHead, rightHead, len);
}
private:
void split(ListNode* inHead, int inLen, ListNode*& outLeftHead, ListNode*& outRightHead)
{
int midIndex = (inLen-1)/2;
ListNode* node = inHead;
for(int i=0;i<midIndex;++i)
{
node = node->next;
}
outLeftHead = node;
outRightHead = node->next;
// Flip the left half of the linked list
ListNode* last = NULL;
ListNode* curr = inHead;
ListNode* next = inHead->next;
for(int i=0;i<=midIndex;++i)
{
curr->next = last;
last = curr;
curr = next;
next = next ? next->next:NULL;
}
outLeftHead = last;
}
bool isPalindrome(ListNode* leftHead, ListNode* rightHead, int len)
{
ListNode* leftNode = leftHead;
ListNode* rightNode = rightHead;
if((len & 0x1) == 1)
{
leftNode = leftNode->next;
}
while(leftNode)
{
if(leftNode->val != rightNode->val)
{
return false;
}
leftNode = leftNode->next;
rightNode = rightNode->next;
}
return true;
}
// get rid of the influence on the original linked list caused by split
void restore()
{}
};
```