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

快慢指针，进行翻转
/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        auto fast = head,slow = head;
        while(fast){
            if(fast->next == nullptr)break;
            fast = fast->next->next;
            slow = slow->next;
        }
        //翻转链表
        reverse(slow);
        //然后让快指针指向相应的位置
        fast = slow->next;
        slow = head;//慢指针从头开始
        while(fast){
            if(slow->val != fast->val)return false;
            slow = slow->next;fast = fast->next;
        }
        return true;
    }
    void reverse(ListNode *head){
        auto prev = head,current = head->next;
        while(current){
            auto next = current->next;
            if(next == nullptr)return;
            current->next = next->next;
            next->next = prev->next;
            prev->next = next;
        }
    }
};