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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    bool isPail(ListNode* head) {
        if(head==nullptr||head->next==nullptr){
            return true;
        }
        ListNode* n1=head;
        ListNode* n2=head;
        while(n2->next!=nullptr&&n2->next->next!=nullptr){//在判断这个边界条件的时候，一定要判断快指针的，慢的永远赶不上快的；
              n1=n1->next;
              n2=n2->next->next;
        }
	  //将链表中点的右端反转
        n2=n1->next;
        n1->next=nullptr;
        ListNode* n3=nullptr;
        while(n2!=nullptr){
            n3=n2->next;
            n2->next=n1;
            n1=n2;
            n2=n3;
        }
        n3=n1;
        n2=head;
        bool ans=true;
        while(n1!=nullptr&&n2!=nullptr){
            if(n1->val!=n2->val){
                ans=false;
                break;
            }
            n1=n1->next;
            n2=n2->next;
        }
	  //还原链表
        n2=n3->next;
        n3->next=nullptr;
        while(n2!=nullptr){
            n1=n2->next;
            n2->next=n3;
            n3=n2;
            n2=n1;
        }
        return ans;
    }
};