写一个函数，实现链表的排序（使链表中元素的从无序到有序，要求从小到大），使用c语言

在C语言中，我们可以使用插入排序算法来对单链表进行排序。由于链表的节点访问是通过指针进行的，插入排序比较适合这种动态数据结构。这里是一个简单的插入排序链表实现示例： ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构 typedef struct Node { int data; struct Node* next; } Node; // 插入节点函数，用于排序 Node* insertSorted(Node* head, int value) { if (head == NULL || head->data > value) { // 如果头节点为空或者新值小于当前头节点，则将新值作为头节点 Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = head; return newNode; } else { // 否则，在已排序的部分找到合适的位置插入 Node* current = head; while (current->next != NULL && current->next->data < value) { current = current->next; } Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = current->next; current->next = newNode; return head; } } // 主函数，演示链表排序过程 void sortLinkedList(Node** head) { if (*head == NULL) return; // 空链表无需排序 Node* sortedList = *head; Node* temp = NULL; while(sortedList->next != NULL) { temp = sortedList; sortedList = sortedList->next; // 使用insertSorted函数插入并保持链表有序 sortedList = insertSorted(temp, sortedList->data); } // 将最后剩余的一个节点连接回原链表的尾部 temp->next = sortedList; } // 打印链表 void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } int main() { // 初始化链表示例 Node* unsortedList = (Node*)malloc(sizeof(Node)); unsortedList->data = 5; Node* secondNode = (Node*)malloc(sizeof(Node)); secondNode->data = 2; Node* thirdNode = (Node*)malloc(sizeof(Node)); thirdNode->data = 9; unsortedList->next = secondNode; secondNode->next = thirdNode; printf("Original unsorted list:\n"); printList(unsortedList); sortLinkedList(&unsortedList); printf("\nSorted list:\n"); printList(unsortedList); return 0; } ``` 在这个例子中，`sortLinkedList`函数会递归地遍历整个链表，利用`insertSorted`函数插入每个节点，直到链表变得完全有序。记得在实际应用中处理内存分配和释放。