M234.回文链表

linked list, https://leetcode.cn/problems/palindrome-linked-list/

请用快慢指针实现 O(1) 空间复杂度。

思路：用快慢指针找出链表中间的地址，反转中间往后的链表，再查即可，用时约15Min

class Solution 
{
public:
    //中间指针
    ListNode* midnote(ListNode* head)
    {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    //反转中间后面的
    void reverse(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head->next;
        while (cur != nullptr)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        head->next = pre;
    }

    bool isPalindrome(ListNode* head) 
    {
        ListNode* mid = midnote(head);
        reverse(mid);
        while (head != nullptr && mid->next != nullptr)
        {
            if (head->val != mid->next->val)
                return false;
            head = head->next;
            mid = mid->next;
        }
        return true;
    }
};