题解 | #牛群编号的回文顺序#

class Solution {
public:
    // 解题思路：1，利用快慢指针找到链表的中点
    //          2，利用定义的反转链表函数，把中点以后的链表反转
    //          3，利用指针遍历来比较中点前后的链表
    // 链表反转
    ListNode* ReverseList(ListNode* h){
        if(h == nullptr || h->next == nullptr){
            return h;
        }
        ListNode* pre = nullptr;
        ListNode* currrent = h;
        while(currrent){
            ListNode* temp = currrent->next;
            currrent->next = pre;
            pre = currrent;
            currrent = temp;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        // write code here
        if(head == nullptr || head->next == nullptr){
            return true;
        }
        // 利用快慢指针，一步两步地获取链表的中点
        ListNode* midle = head;
        ListNode* right = head;
        while(right != nullptr && right->next != nullptr){
            midle = midle->next;
            right = right->next->next;
        }
        // 从中点开始反转操作
        ListNode* RL = ReverseList(midle);
        // 开始遍历比较
        while(RL != nullptr){
            if(head->val != RL->val){
                return false;
            }
            RL = RL->next;
            head = head->next;
        }
        return true;
    }
};