如何用C语言实现链表的排序？

在C语言中实现链表的排序通常会使用一种叫做“插入排序”的简单算法，因为链表不适合直接使用复杂排序算法（如快速排序、归并排序等），它们依赖于随机访问，而链表则是顺序访问。

以下是使用插入排序对单向链表进行升序排序的一个基本步骤：

1. 定义一个辅助函数`insert_sorted`，用于将新节点插入到已排序的部分，保证链表的有序性。

2. 定义一个主函数`sort_list`，首先创建一个新的头结点`sorted_head`和`current`指针指向原头结点。

3. 使用`while`循环遍历链表，当`current`不为空时：
a. 获取当前节点的值`temp Val`。
b. 创建一个临时指针`prev`，初始化为`sorted_head`。
c. 同样遍历已排序部分的链表，直到找到一个大于等于`temp Val`的节点或遍历完，将`prev`指向前一个大于等于`temp Val`的节点。
d. 如果`prev`未改变，则说明`temp Val`应该作为新的头结点；否则，将`temp`链接到`prev`之后。

4. 遍历结束后，将原头结点指向`sorted_head`，完成链表排序。

typedef struct Node {
    int data;
    struct Node *next;
} Node;

void insert_sorted(Node **sorted_head, Node *new_node) {
    if (*sorted_head == NULL || new_node->data <= (*sorted_head)->data) {
        new_node->next = *sorted_head;
        *sorted_head = new_node;
    } else {
        Node *current = *sorted_head;
        while (current->next != NULL && current->next->data < new_node->data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

void sort_list(Node **head) {
    Node *sorted_head = NULL, *current = *head, *temp;
    while (current != NULL) {
        temp = current;
        current = current->next;
        insert_sorted(&sorted_head, temp);
    }
    *head = sorted_head;
}