在单链表上实现顺序排序，用c++

在单链表上实现顺序排序，例如升序排列，可以使用冒泡排序、插入排序、选择排序等简单算法，因为它们不需要额外的存储空间。这里我们以插入排序为例，它适合于链表数据结构，因为我们可以直接通过指针操作节点。

**插入排序链表算法步骤：**
1. 定义两个指针，`current` 和 `previous` 分别指向当前节点和前一个节点，初始时都设置为`NULL`。
2. 遍历链表，从第二个节点开始（假设为`node`）。
3. 对每个节点`node`，比较其值`val`与前一个节点`previous.val`，如果`val`小于`previous.val`，则交换两个节点的位置。
4. 更新`previous`和`current`，继续遍历到下一个节点，直到遍历完整个链表。
5. 最终链表会按照升序排列。

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

ListNode* insertionSortList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    ListNode* current = head->next;
    while (current != nullptr) {
        ListNode* previous = current;
        ListNode* nextTemp = current->next;

        if (current->val < previous->val) {
            previous->next = current->next;
            current->next = previous;
            current = nextTemp;
        } else {
            previous = current;
            current = nextTemp;
        }
    }

    return head;
}