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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    //返回链表中间结点
    ListNode* midnode(ListNode* head)
    {
        ListNode*fast=head;
        ListNode*slow=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    //逆置链表
    ListNode* reverselist(ListNode* head)
    {
        ListNode*n1=nullptr;
        ListNode*n2=head;
        ListNode*n3=n2->next;
        if(head==nullptr)
            return head;
        while(n2)
        {
            n2->next=n1;
            n1=n2;
            n2=n3;
            if(n3)
                n3=n3->next;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) 
    {
        ListNode*head=A;
        ListNode*mid=midnode(A);
        ListNode*rmid=reverselist(mid);
        while(rmid&&head)
        {
            if(head->val!=rmid->val)
                return false;
            head=head->next;
            rmid=rmid->next;
        }
        return true;
    }
};