题解 | 重排链表，拆分链表并反转，再重新链接

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if (head == nullptr) {
            return;
        }
    
        ListNode *it_1 = head;
        ListNode *it_2 = head;
        ListNode *split_it = nullptr;
        
        while (true) {
            if (it_2 == nullptr) {
                split_it = it_1->next;
                it_1->next = nullptr;
                break;
            } else if (it_2->next == nullptr) {
                split_it = it_1->next;
                it_1->next = nullptr;
                break;
            }

            it_1 = it_1->next;
            it_2 = it_2->next->next;
        }

        if (split_it == nullptr) {
            return;
        }

        ListNode *second_head;
        for (ListNode *it_pre = split_it, *it_cur = split_it->next;;) {
            if (it_cur == nullptr) {
                second_head = it_pre;
                break;
            }

            ListNode *it_post = it_cur->next;
            it_cur->next = it_pre;
            it_pre = it_cur;
            it_cur = it_post;
        }
        split_it->next = nullptr;

        for (ListNode *fst_it = head, *sec_it = second_head;;) {
            if (sec_it == nullptr) {
                break;
            }

            ListNode *fst_post_it = fst_it->next;
            ListNode *sec_post_it = sec_it->next;

            sec_it->next = fst_post_it;
            fst_it->next = sec_it;
            
            fst_it = fst_post_it;
            sec_it = sec_post_it;
        }
    }
};

遍历找出中间节点，将链表一分为二，再将第二条链表反转，再按顺序合并两条链表。满足空间及时间复杂度要求。