要求时间复杂度$O(n)$，空间复杂度$O(1)$

①找到链表的中间元素。（遍历两遍或力扣官方题解使用的快慢指针都可以）

②翻转后半段链表。

③两个链表节点数量相等或前半段多一个，直接合并。

struct ListNode* reverse(struct ListNode *head){
    struct ListNode* pre = NULL, *curr = head;
    while(curr!= NULL){
        struct ListNode *next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}
void reorderList(struct ListNode* head) {
    int tot = 0;
    struct ListNode* curr = head;
    while(curr != NULL){
        curr = curr->next;
        tot++;
    }
    int mid;
    if(tot & 1 == 1)mid = (tot >> 1) + 1;
    else mid = tot >> 1;
    mid--;
    curr = head;
    while(mid){
        curr = curr->next;
        mid--;
    }
    struct ListNode* head2 = reverse(curr->next);
    curr->next = NULL;
    curr = head;
    while(head2 != NULL){
        struct ListNode* next = curr->next;
        curr->next = head2;
        curr = head2;
        head2 = next;
    }
}