c++单链表递增排序

在C++中，对单链表进行递增排序通常涉及到链表的遍历、节点比较以及交换操作。以下是一个简单的步骤：

1. 定义结构体（例如`Node`），包含一个整数值`value`和指向下一个节点的指针`next`。

struct Node {
    int value;
    Node* next;
};

2. 创建一个函数，用于递归地将列表分为两部分：小于当前值的部分和大于等于当前值的部分。这里可以使用快慢指针找到中间点。

void partition(Node** head, int val, Node** smaller, Node** larger) {
    if (*head == nullptr) return;

    *smaller = nullptr;
    *larger = nullptr;
    while (*head != nullptr) {
        if (*head->value < val) {
            if (*smaller == nullptr) *smaller = *head;
            else *smaller->next = *head;
            *smaller = *head;
        } else {
            if (*larger == nullptr) *larger = *head;
            else *larger->next = *head;
            *larger = *head;
        }
        *head = *head->next;
    }
}

3. 主函数中，创建两个临时头结点`smaller`和`larger`，然后开始从原链表头部进行分区。

void insertionSortList(Node*& head) {
    if (head == nullptr || head->next == nullptr) return; // 如果链表为空或只有一个元素，无需排序

    Node* pivot = head->next;
    partition(&head, pivot->value, &smaller, &pivot);
    insertionSortList(smallerc); // 对较小部分递归排序
    insertionSortList(largerc); // 对较大部分递归排序
    pivot->next = nullptr; // 将分割后的链表连接起来
    if (smallerc) {
        smallerc->next = head;
        head = smallerc;
    }
}