描述

给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 0 \le n \le 10^70≤n≤107，链表中每个节点的值满足 |val| \le 10^7∣val∣≤107.

普通字符串回文因为可以直接获得长度，直接利用双指针，一个从头往尾，一个从尾往前，很好解决。
因为是单向链表，不能从后往前遍历，所以我们得想办法让其中一个指针从后往前。
很容易想到反转链表，但是反转链表是整个反转，显然不能解决问题。
从题目出发，回文是从前往中间和从后往中间的字符完全一样，那么我们怎么找到这个中间呢，
利用快慢指针，慢指针每次只走一步，而快指针每次走两步，当快指针指向null，或者快指针的下一个指向null时，
slow->next就是我们需要反转的开始，让fast指向slow->next,并且从fast开始反转链表。
反转结束会后，让慢指针重新指向头节点。
接着逐个比较快慢指针（此时快指针每次也只走一步）的值，遇到值不同时，说明不是回文，返回false。
如果一直比较到快指针到null还没有返回false，说明已经比较完且每个值都相同，返回true。 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    bool isPail(ListNode* head) {
        // write code here
        if(head==NULL||head->next==NULL) return true;
        ListNode *slow,*fast;
        slow=head,fast=head->next;
        while(fast->next!=NULL&&fast!=NULL) slow=slow->next,fast=fast->next->next;
        fast=slow->next,slow=head;
        fast=ReveseList(fast);
        while(fast!=NULL) {
            if(slow->val!=fast->val) return false;
            slow=slow->next;
            fast=fast->next;
        }
        return true;
    }
public: ListNode* ReveseList(ListNode* Head) {
        ListNode* p=NULL;
        ListNode* q=NULL;
        while(Head!=NULL)
        {
            q=Head;
            Head=Head->next;
            q->next=p;
            p=q;
        }
        return p;
    }
};