C++链表插入排序代码

在C++中，链表不支持随机访问元素，因此不适合直接使用插入排序。但如果你坚持要在链表上实现插入排序，你可以遍历链表，对于每一个节点，将其值插入到已经排序的部分中的正确位置。以下是简单的插入排序链表的示例代码：

#include <iostream>

// 链表节点定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void insertionSortList(ListNode** head) {
    ListNode* sorted = nullptr; // 已排序部分的头指针
    ListNode* current = *head; // 当前待排序节点

    while (current != nullptr) {
        ListNode* nextToInsert = current->next; // 记录下一个待插入的节点

        // 将当前节点插入已排序链表
        if (sorted == nullptr || current->val <= sorted->val) {
            current->next = sorted;
            sorted = current;
        } else {
            ListNode* prev = sorted;
            while (prev->next != nullptr && prev->next->val < current->val) {
                prev = prev->next;
            }
            current->next = prev->next;
            if (prev->next != nullptr) {
                prev->next = current;
            } else {
                sorted = current;
            }
        }

        current = nextToInsert; // 移动到下一个待排序的节点
    }
    *head = sorted; // 更新链表头指针
}

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

int main() {
    // 创建一个链表
    ListNode* list = new ListNode(4);
    list->next = new ListNode(2);
    list->next->next = new ListNode(1);
    list->next->next->next = new ListNode(3);

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

    insertionSortList(&list);

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

    return 0;
}