Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

思路：将链表前半部分反转，对比就行了。

 1 class Solution {
 2 public:
 3     bool isPalindrome(ListNode* head) {
 4         if (head == NULL || head->next == NULL)
 5             return true;
 6         int count = 1;
 7         ListNode prenode(-1);
 8         prenode.next = head;
 9         ListNode *cur = head, *nex, *pre = &prenode;
10         while (cur = cur->next)
11             count++;
12         cur = head;
13         nex = cur->next;
14         for (int i = 1; i < count / 2; i++)
15         {
16             cur->next = nex->next;
17             nex->next = pre->next;
18             pre->next = nex;
19             nex = cur->next;
20         }
21         if (count % 2) nex = nex->next;
22         cur = pre->next;
23         for (int i = 1; i <= count / 2; i++, cur = cur->next, nex = nex->next)
24             if (cur->val != nex->val) return false;  
25         return true;
26     }
27 };