单链表C++的插入排序

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

ListNode* insertionSortList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    ListNode* dummy = new ListNode(0);  // 创建一个虚拟头节点
    dummy->next = head;
    ListNode* curr = head->next;  // 当前待插入节点
    head->next = nullptr;  // 将原链表拆分为已排序和未排序两部分
    
    while (curr != nullptr) {
        ListNode* prev = dummy;
        while (prev->next != nullptr && prev->next->val < curr->val) {
            prev = prev->next;
        }
        
        ListNode* next = curr->next;  // 保存下一个待插入节点
        curr->next = prev->next;
        prev->next = curr;
        curr = next;
    }
    
    ListNode* sortedList = dummy->next;
    delete dummy;
    return sortedList;
}