按升序对链表进行排序并打印排序的列表

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

ListNode* head = nullptr;  // 创建一个空链表

// 向链表中插入节点
void insertNode(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// 归并排序链表
ListNode* mergeSort(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode* mid = slow->next;
    slow->next = nullptr;
    
    ListNode* left = mergeSort(head);
    ListNode* right = mergeSort(mid);
    
    return merge(left, right);
}

// 对链表进行排序并返回排序后的头节点
ListNode* sortList(ListNode* head) {
    return mergeSort(head);
}

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

#include <iostream>
using namespace std;

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

// 向链表中插入节点
void insertNode(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// 归并排序链表
ListNode* mergeSort(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode* mid = slow->next;
    slow->next = nullptr;
    
    ListNode* left = mergeSort(head);
    ListNode* right = mergeSort(mid);
    
    return merge(left, right);
}

// 对链表进行排序并返回排序后的头节点
ListNode* sortList(ListNode* head) {
    return mergeSort(head);
}

// 打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = nullptr;  // 创建一个空链表
    
    // 向链表中插入节点
    insertNode(head, 3);
    insertNode(head, 1);
    insertNode(head, 2);
    insertNode(head, 5);
    insertNode(head, 4);
    
    cout << "原始链表：";
    printList(head);
    
    head = sortList(head);
    
    cout << "排序后的链表：";
    printList(head);
    
    return 0;
}