1. 使用快慢指针找中点的原理是fast和slow两个指针，每次快指针走两步，慢指针走一步，等快指针走完时，慢指针的位置就是中点。如果是偶数个数，正好是一半一半，如果是奇数个数，慢指针正好在中间位置，判断回文的时候不需要比较该位置数据。
注意好好理解快慢指针的算法原理及应用。
2. 每次慢指针走一步，都把值存入栈中，等到达中点时，链表的前半段都存入栈中了，由于栈的后进先出的性质，就可以和后半段链表按照回文对应的顺序比较。
solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(!head || !head->next) return true;
stack<int> prehalf;
ListNode *fast = head, *slow = head;
prehalf.push(head->val);
while(fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
prehalf.push(slow->val);
}
if(!fast->next) prehalf.pop();
while(slow->next)
{
slow = slow->next;
if(slow->val != prehalf.top()) return false;
prehalf.pop();
}
return true; }
};
要求使用O(1)的空间，那就是不能使用stack了，那么如何代替stack的作用呢，用stack的目的是为了利用其后进先出的特点，以便倒着取出前半段的元素。那么现在不用stack了，如何倒着取元素呢？可以在找到中点后，将后半段的链表翻转一下，这样就可以按照回文的顺序比较了。
solution:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL || head->next==NULL) return true;
ListNode *slow=head, *fast=head;
while((fast->next) && (fast->next->next))
{
slow = slow->next;
fast = fast->next->next;
}
//reverse last.
ListNode *last = slow->next, *pre = head;
ListNode *reverse = NULL;
while(last)
{
ListNode *tmp = last;
last = tmp->next;
tmp->next = reverse;
reverse = tmp;
}
//compare pre and reverse.
while(reverse)
{
if(reverse->val != pre->val) return false;
pre = pre->next;
reverse = reverse->next;
}
return true; }
};
注意这个解决方法在翻转链表的过程中容易出错，一定要熟练掌握链表翻转的操作过程！！！
参考
1. GrandYang;
完