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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
 #include <math.h>
#include <stdbool.h>
#include <stdlib.h>
struct ListNode* resvers(struct ListNode* pHead)
 {
    struct ListNode *p0, *p1, *p2;
    if(pHead == NULL || pHead->next == NULL)
    {
        return pHead;
    }

    p0 = pHead;
    p2 = NULL;
    while(p0)
    {
        p1 = p0->next;
        p0->next = p2;
        p2 = p0;
        p0 = p1;
    }
    return p2;
 }
bool isPail(struct ListNode* head ) {
    // write code here
    //时间复杂度为O(n2)
    // struct ListNode* first = head;
    // struct ListNode* second;

    // if(head == NULL)
    // {
    //     return NULL;
    // }
    // if(head->next == NULL)
    // {
    //     return true;
    // }

    // second = resvers(head);
    // while (first && second) 
    // {
    //     int val1 = first->val;
    //     int val2 = second->val;
    //     if(val1 != val2)
    //     {
    //         return false;
    //     }
    //     first = first->next;
    //     second = second->next;
    // }
    // return true;
//有一个bug，当输入1,2,3,4,2,1时，还是判断为正确。
    // struct ListNode *fast = head, *slow = head;
    // while(fast != NULL && fast->next != NULL)
    // {
    //     fast = fast->next->next;
    //     slow = slow->next;
    // }
    // struct ListNode* cur = slow->next;
    // slow->next = NULL;
    // struct ListNode* p0;
    // p0 = resvers(cur);

    // while(p0 != NULL)
    // {
    //     if(p0->val != head->val)
    //     {
    //         return false;
    //     }
    //     p0 = p0->next;
    //     head = head->next;
    // }
    // return  true;

    struct ListNode* p1 = head;
    int ListLength = 0;//记录链表节点个数
    int count = 1;//记录链表前半段节点个数
    if(head == NULL)
    {
        return NULL;
    }
    if(head->next == NULL)
    {
        return true;
    }
    while(p1 != NULL)
    {
        ListLength++;
        p1 = p1->next;
    }
    struct ListNode* slow = head;
    while(count < ListLength/2)  
    {
        count++;
        slow = slow->next;
    }
    struct ListNode* cur = slow->next;//指向链表后半段
    struct ListNode* p2 = resvers(cur);//翻转链表后半段
    while(p2 != NULL)
    {
        if(p2->val != head->val)
        {
            return false;
        }
        p2 = p2->next;
        head = head->next;
    }
    return true;


}