题解 | #判断一个链表是否为回文结构#

普通循环的方式总是运行太慢，只要由两层循环就不得行。

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */

bool isPail(struct ListNode* head ) {
    // write code here  
    struct ListNode* pfast; //快指针
    struct ListNode* pslow;//慢指针
    struct ListNode* pnex;//后面一个指针
    pfast = head;
    pslow = head;
    pnex = NULL;
    if(head==NULL || head->next==NULL)
    {
        return true;
    }
    while(pfast!=NULL && pfast->next!=NULL)
    {
        pfast = pfast->next->next;
        pslow = pslow->next;
    }
    pfast = pslow->next;
    pslow->next=NULL;
    while(pfast!=NULL)
    {
        pnex = pfast->next;
        pfast->next = pslow;
        pslow = pfast;
        pfast = pnex;
    }
    pfast = head;
    while(pslow!=NULL && pfast!=NULL)
    {
        if(pslow->val!=pfast->val)
        {
            return false;
        }
        pfast = pfast->next;
        pslow = pslow->next;
    }
    return true;
    //只要循环n/2次
//     for(int i=0;i<(n/2);i++)
//     {
//         j = 0;
//         while(j<(n-i-1))
//         {
//             p2 = p2->next;
//             j++;
//         }
//         if(p1->val == p2->val)
//         {
//             p1 = p1->next;
//             p2 = head;
//         }
//         else
//         {
//             return false;
//         }
//     }
}