思路：
1. 先寻找链表的中点，将其一分为二；
2. 反转后半段链表;
3. 遍历两段链表，合并。

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr) return;

        auto mid = findMid(head);               //找到中点
        auto l1 = head, l2 = mid->next;
        mid->next = nullptr;                    //中点后截断，分成两条链表
        l2 = reverseList(l2);                   //反转后半段链表

        merge(l1, l2);        
    }

    ListNode* findMid(ListNode* head)           //双指针找链表中点
    {
        auto fast = head, slow = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* head)       //反转链表
    {
        if (head == nullptr) return nullptr;

        auto pre = head, cur = head->next;
        while (cur)
        {
            auto ne = cur->next;
            cur->next = pre;
            pre = cur, cur = ne;
        }

        head->next = nullptr;
        return pre;
    }

    void merge(ListNode* l1, ListNode* l2)      //合并链表
    {
        while (l1 && l2)
        {
            auto p1 = l1->next, p2 = l2->next;  //先保存两条链表的下一个节点

            l1->next = l2;
            l1 = p1;                            //L1往下走一步，即L1 = L1->next

            l2->next = l1;
            l2 = p2;                            //L2往下走一步，即L2 = L2->next
        }
    }
};