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

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

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

struct ListNode* middleNode(struct ListNode* pHead ) {
    struct ListNode *fast, *slow;
    fast = slow = pHead;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode* ReverseList(struct ListNode* pHead ) {
    struct ListNode* cur = pHead;
    struct ListNode* newhead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

bool isPail(struct ListNode* head ) {
    struct ListNode* mid = middleNode(head);
    struct ListNode* rhead = ReverseList(mid);
    struct ListNode* cur = head;
    struct ListNode* curR = rhead;
    while(cur && curR)
    {
        if(cur->val != curR->val)
            return false;
        else{
            cur = cur->next;
            curR = curR->next;
        }
    }
    return true;
}