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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow,* fast;
    slow=fast=head;
    while(fast!=NULL && fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur=head,*newhead=NULL;
    while(cur)
    {
        struct ListNode* next=cur->next;

        //头插
        cur->next=newhead;
        newhead=cur;//更新头节点

        cur=next;
    }
    return newhead;
}

    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid=middleNode(A);//找中间节点
        struct ListNode* rmid=reverseList(mid);//逆置后半段
        struct ListNode* cur=A;
        while(cur && rmid)
        {
            if(cur->val!=rmid->val)
            {
                return false;
            }
            else 
            {
                cur=cur->next;
                rmid=rmid->next;
            }
        }
        return true;
    }
};