输入一个偶数n，建立不带头节点的整数单链表l,重新排列单链表l的节点顺序

思路：

1. 将单链表l按照从小到大的顺序排序。
2. 将单链表l的前一半节点（即前n/2个节点）依次作为新链表的节点。
3. 将单链表l的后一半节点（即后n/2个节点）依次插入到新链表的每个节点之后。

代码实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

void insert(ListNode* &head, int x) {
    ListNode* node = new ListNode(x);
    if (head == NULL) {
        head = node;
        return;
    }
    ListNode* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = node;
}

void printList(ListNode* head) {
    ListNode* p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

ListNode* mergeList(ListNode* p1, ListNode* p2) {
    ListNode* head = NULL;
    ListNode* p = NULL;
    while (p1 != NULL && p2 != NULL) {
        if (p1->val < p2->val) {
            if (head == NULL) {
                head = p = p1;
            }
            else {
                p->next = p1;
                p = p->next;
            }
            p1 = p1->next;
        }
        else {
            if (head == NULL) {
                head = p = p2;
            }
            else {
                p->next = p2;
                p = p->next;
            }
            p2 = p2->next;
        }
    }
    if (p1 != NULL) {
        if (head == NULL) {
            head = p1;
        }
        else {
            p->next = p1;
        }
    }
    if (p2 != NULL) {
        if (head == NULL) {
            head = p2;
        }
        else {
            p->next = p2;
        }
    }
    return head;
}

void reorderList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    ListNode* p1 = head;
    ListNode* p2 = head->next;
    while (p2 != NULL && p2->next != NULL) {
        p1 = p1->next;
        p2 = p2->next->next;
    }
    ListNode* mid = p1->next;
    p1->next = NULL;
    ListNode* p3 = NULL;
    while (mid != NULL) {
        ListNode* tmp = mid->next;
        mid->next = p3;
        p3 = mid;
        mid = tmp;
    }
    ListNode* p = head;
    while (p3 != NULL) {
        ListNode* tmp = p3->next;
        p3->next = p->next;
        p->next = p3;
        p = p3->next;
        p3 = tmp;
    }
}

int main() {
    int n;
    cin >> n;
    ListNode* head = NULL;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        insert(head, x);
    }
    reorderList(head);
    printList(head);
    return 0;
}