class Solution {
public:
    void reorderList(ListNode* head) {
        vector<ListNode*> arr;
        ListNode* p = head;
        while (p != nullptr) {
            arr.push_back(p);
            p = p->next;
        }
        int tail = arr.size() - 1;
        p = head;
        for (int i = 0; i < (arr.size() - 1) / 2; i++) {
            ListNode* t = p->next;
            arr[tail]->next = t;
            p->next = arr[tail];
            tail -= 1;
            arr[tail]->next = nullptr;
            p = t;
        }
    }
};