单链表插入排序 ###目的： 掌握单链表的应用和插入排序的思想。 ###内容： 编写一个函数insertion_sort，对一个无序单链表采用插入排序的方式，将其按递增方式排序，构成有序单链表。系统后

单链表的插入排序是一种简单的排序算法，它的工作原理类似于我们对扑克牌进行排序的过程。基本思路是将链表分为已排序和未排序两个部分，初始时已排序的部分只包含链表的第一个节点。然后，逐个取出未排序部分的节点，将它们插入到已排序部分的合适位置上，直到所有节点都被排序。

在单链表中实现插入排序，你需要定义一个排序函数`insertion_sort`，该函数接收链表的头节点作为参数。排序的基本步骤如下：

1. 从链表的第二个节点开始，逐个取出后面的节点。
2. 对于取出的节点，先检查它前面的节点（已排序部分），如果该节点的值比它小，则继续向前查找，直到找到合适的位置插入。
3. 将取出的节点插入到已排序部分的正确位置上。
4. 重复上述过程，直到链表中的所有节点都已插入到已排序部分，此时链表已经排序完成。

这里是一个简化的示例代码框架，用于说明如何对单链表进行插入排序：

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

void insertion_sort(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return; // 链表为空或只有单个节点时不需要排序
    }

    ListNode *sorted = NULL; // 已排序部分的头节点
    ListNode *current = head; // 正在处理的节点

    while (current != NULL) {
        ListNode *next = current->next; // 保存当前节点的下一个节点
        // 插入当前节点到已排序部分
        if (sorted == NULL || sorted->val > current->val) {
            // 插入到已排序链表的头部
            current->next = sorted;
            sorted = current;
        } else {
            // 找到已排序部分中合适的插入位置
            ListNode *sortedCurrent = sorted;
            while (sortedCurrent->next != NULL && sortedCurrent->next->val < current->val) {
                sortedCurrent = sortedCurrent->next;
            }
            // 插入当前节点
            current->next = sortedCurrent->next;
            sortedCurrent->next = current;
        }
        current = next; // 移动到下一个节点
    }
}

在上述代码中，我们创建了一个新的节点`current`来遍历原始链表，同时`sorted`节点作为已排序部分的头部。我们不断地将`current`节点插入到`sorted`链表的合适位置，直到整个链表被排序。