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

class PalindromeList {
public:
    ListNode* reverse(ListNode *A){
        if(A->next == nullptr){
            return A;
        }
        ListNode * fastP = A -> next;
        ListNode * slowP = A;
        while(fastP->next != nullptr){
            ListNode *fastNext = fastP->next;
            fastP->next =slowP;
            slowP = fastP;
            fastP = fastNext;
        }
        A ->next =nullptr;
        return fastP;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        if(A->next == nullptr){
            return false;
        }
        if(A->next->next ==nullptr ){
            if(A->val == A->next->val){
                return true;
            }
            return false;
        }
        ListNode * begin = A;
        ListNode * fastP = A;
        ListNode * slowP = A;
        while(fastP->next!= nullptr && fastP->next->next != nullptr  ){
            fastP = fastP->next->next;
            slowP = slowP->next;
        }
        
            slowP = slowP -> next; //奇数 偶数都需要处理
        
        ListNode* reverseList = reverse(slowP);
        while(reverseList != nullptr && begin !=nullptr){
            if(reverseList -> val != begin ->val){
                return false;
            }
            reverseList = reverseList->next;
            begin =begin->next;
        }
        return true;
    }
};