c++用类单链表实现插入排序

在C++中，使用类单链表实现插入排序的基本思路是通过遍历链表，逐个取出节点，并将其插入到已排序部分的新链表中，这样就保持了插入节点的有序性。以下是实现这个算法的步骤：

1. 创建一个空的类单链表作为已排序部分的链表。
2. 遍历原始链表，对于每个节点，将其插入到已排序链表中的正确位置。
3. 在插入过程中，需要维护一个指向已排序链表中最后一个节点的指针，以便能够将新节点插入到链表尾部。
4. 重复这个过程，直到原始链表为空，排序完成。

下面是一个简单的类定义和插入排序的函数实现：

#include <iostream>

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

class LinkedList {
public:
    ListNode *head;
    LinkedList() : head(NULL) {}

    // 插入节点到已排序链表中
    void sortedInsert(ListNode *&sortedHead, ListNode *newNode) {
        ListNode *current = sortedHead;
        // 创建一个哑节点，方便处理插入头节点的情况
        ListNode *prev = new ListNode(0);

        // 查找插入位置
        while (current != NULL && current->val < newNode->val) {
            prev = current;
            current = current->next;
        }

        // 插入节点
        newNode->next = current;
        prev->next = newNode;

        // 如果插入的是第一个节点，更新排序链表的头节点
        if (prev == sortedHead) {
            sortedHead = newNode;
        }
    }

    // 插入排序函数
    void insertionSort() {
        if (head == NULL || head->next == NULL) {
            return;
        }

        ListNode *sortedHead = new ListNode(0);
        ListNode *current = head;

        while (current != NULL) {
            ListNode *next = current->next;
            sortedInsert(sortedHead, current);
            current = next;
        }

        head = sortedHead->next; // 重设头节点为已排序链表的头节点
        delete sortedHead; // 删除哑节点
    }

    // 打印链表函数
    void printList() {
        ListNode *current = head;
        while (current != NULL) {
            std::cout << current->val << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    // 示例使用插入排序
    LinkedList list;
    // 假设这里是链表的初始化和添加节点的过程
    // ...

    list.insertionSort();
    list.printList(); // 打印排序后的链表

    return 0;
}

以上代码定义了一个`ListNode`类作为链表节点，以及一个`LinkedList`类来实现链表的插入排序。`sortedInsert`方法用于将节点插入到已排序的链表中，而`insertionSort`方法则是用来执行整个排序过程。