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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
     //---------转数组---------
    // bool isPail(ListNode* head) {
    //     if(head->next==NULL)
    //         return true;
    //     vector<int>x;
    //     while(head!=NULL)
    //     {
    //         x.push_back(head->val);
    //         head=head->next;
    //     }
    //     int n=x.size();

    //     for(int i=0;i<n/2;i++)
    //     {
    //         if(x[i]!=x[n-i-1])
    //             return false;
    //     }
    //     return true;
    // }
    //-------翻转链表----------
    //翻转链表
    ListNode* Reverse(ListNode* head)
    {
        ListNode* prev=NULL;
        ListNode* cur=head;
        while(cur!=NULL)
        {
            ListNode* next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
    bool isPail(ListNode* head)
    {
        if(head==NULL||head->next==NULL)
            return true;
        //使用快慢指针寻找中心位置
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast->next!=NULL&&fast->next->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* p2=Reverse(slow->next);
        ListNode* p1=head;
        while(p1!=NULL&&p2!=NULL)
        {
            if(p1->val!=p2->val)
               return false;
            p1=p1->next;
            p2=p2->next;
        }
        return true;
    }

   
};