class Solution {
public:
    void rearrangedList(ListNode* head) {
        int n = 0;

        auto p = head;
        while (p) n++, p = p->next;

        p = head;
        for (int i = 0; i < n / 2; i++)
            p = p->next;

        // len(p) >= len(q)
        auto q = p->next;
        p->next = nullptr;

        if (q) {
            // reverse q
            auto t = q->next;
            q->next = nullptr;
            while (t) {
                auto tt = t->next;
                t->next = q;
                q = t;
                t = tt;
            }
        }

        // cross merge
        p = head;
        while (q) {
            auto t = p->next;
            p->next = q;
            auto tt = q->next;
            q->next = t;
            q = tt;
            p = t;
        }
    }
};