题解 | #链表的回文结构#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

struct ListNode* MiddleNode(struct ListNode* A)
{
    struct ListNode* fast = A;
    struct ListNode* slow = A;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        if(A == NULL || A->next ==NULL )
        {
            return true;
        }
        struct ListNode* mid = MiddleNode(A);//寻找中间结点
        struct ListNode* curr = mid;
        struct ListNode* pre = NULL;
        while(curr)
        {
            struct ListNode* temp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = temp;
        }//逆置中间结点后的结点，此时pre指向链表尾
        while(pre && A)
        {
            if(pre->val == A->val)
            {
                pre = pre->next;
                A = A->next;
            }//遍历两部分结点的值
            else
            return false;//有不相等的值
        }
        return true;//所有都相等
    }
};