// vector 存储链表数据，然后从中间向两头扫描，控制好中间点的坐标即可。
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> arr;
        for (auto cur = head; cur; cur = cur->next) {
            arr.push_back(cur->val);
        }

        int len = arr.size();
        int idx = len / 2;
        int left = 0, right = 0;
        if (len % 2 == 0) {
            left = idx - 1;
            right = idx;
        } else {
            left = right = idx;
        }

        while(left >= 0 && right <= len) {
            if (arr[left] == arr[right]) {
                left--;
                right++;
            }else {
                return false;
            }
        }

        return true;
    }
};

// 最优解法：
// 1. 快慢指针遍历找到链表中间节点。或者一次扫描先计算出长度，再扫描到中间节点。
// 2. 反转后半个链表。
// 3. 双指针依次进行扫描即可。
class Solution {
public:
    ListNode* reverse(ListNode* cur) {
        if (cur == nullptr) {
            return nullptr;
        }

        ListNode* last = nullptr;
        while(cur->next) {
            auto next = cur->next;
            cur->next = last;
            last = cur;
            cur = next;
        }
        cur->next = last;

        return cur;
    }

    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        auto fast = head, slow = head;
        while(fast->next) {
            fast = fast->next;
            if (fast->next) 
                fast = fast->next;
            slow = slow->next;
        }

        // 反转后面的链表
        auto head2 = reverse(slow);

        // 判断是否是回文
        while(head && head2) {
            if (head->val != head2->val) {
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }

        return true;
    }
};