代码实现带头结点的单链表插入排序

下面是一个示例代码，实现了带头结点的单链表插入排序：

#include <iostream>

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

void insertSort(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }

    ListNode* dummy = new ListNode(0);  // 创建一个虚拟头结点
    dummy->next = head;
    ListNode* cur = head->next;  // 从第二个结点开始遍历
    head->next = nullptr;  // 将原链表拆分

    while (cur != nullptr) {
        ListNode* pre = dummy;
        while (pre->next != nullptr && pre->next->val < cur->val) {
            pre = pre->next;
        }
        ListNode* temp = pre->next;  // 保存下一个结点
        pre->next = cur;  // 插入当前结点
        cur = cur->next;  // cur指针移动到下一个结点
        pre->next->next = temp;  // 连接后续结点
    }

    head = dummy->next;  // 更新头结点
    delete dummy;  // 删除虚拟头结点
}

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

int main() {
    ListNode* head = new ListNode(4);
    ListNode* node1 = new ListNode(2);
    ListNode* node2 = new ListNode(1);
    ListNode* node3 = new ListNode(3);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;

    std::cout << "Before sorting: ";
    printList(head);

    insertSort(head);

    std::cout << "After sorting: ";
    printList(head);

    return 0;
}

这段代码中，我们首先创建了一个带头结点的单链表，并初始化了一些结点。然后，我们使用插入排序算法对链表进行排序，最后打印排序后的链表结果。

希望对你有帮助！