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

题目

题解：使用快慢指针找到链表中点，然后对右边一半进行链表反转，然后对两半逐个进行比较节点值

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
   ListNode *reverse(ListNode *head)//反转链表
   {
       ListNode *pre=nullptr,*next=nullptr;
       while(head)
       {
           next=head->next;
           head->next=pre;
           pre=head;
           head=next;
       }
       return pre;//返回反转链表头节点
   }
    bool isPail(ListNode* head) {
        // write code here
        ListNode *fast=head->next,*slow=head;
        while(fast && fast->next)//快慢指针找到中点
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode *tmp=slow->next;
        slow->next=nullptr;//切割成两半
        ListNode *r=reverse(tmp);//反转链表
        while(head && r)//对两半逐个节点判断
        {
            if(head->val!=r->val)return false;
            head=head->next;
            r=r->next;
        }
        return true;

    }
};