## Summary:

Use **reverseList** function to reverse the list from the middle of the given linked list.

## Example:

Suppose we have a linked list 1->2->3->2->0;

Firstly, reverse the list from the middle. Then we get two lists,

- 1->2->3->2->1
- 0->2

Second, compare the two lists from the beginning to half number of the original list. If there is a difference, return False. Otherwise, in the end, return True.

**NOTE:**

- We need to consider odd length or even length.
- This Algorithm runs in O(n) time and O(1) space.

```
class Solution {
public:
ListNode* reverseList(ListNode* head){
if(head == NULL)
return NULL;
if(head->next == NULL)
return head;
ListNode* curr = head->next;
ListNode* pre = head;
ListNode* post = head->next->next;
pre->next = NULL;
while(curr != NULL){
curr->next = pre;
pre = curr;
curr = post;
if(post != NULL)
post = post->next;
}
return pre;
}
bool isPalindrome(ListNode* head) {
int length = 0;
ListNode* traversal = head;
while(traversal != NULL){
traversal = traversal->next;
length++;
}
traversal = head;
int half = length / 2;
if(length % 2 == 0){
while(half > 0){
traversal = traversal->next;
half--;
}
ListNode* newHead = reverseList(traversal);
half = length / 2;
while(half > 0){
if(newHead->val != head->val)
return false;
newHead = newHead->next;
head = head->next;
half--;
}
return true;
}
else{
while(half > 0){
traversal = traversal->next;
half--;
}
traversal = traversal->next;
ListNode* newHead = reverseList(traversal);
half = length / 2;
while(half > 0){
if(newHead->val != head->val)
return false;
newHead = newHead->next;
head = head->next;
half--;
}
return true;
}
}
};
```