C语言将一个无序链表变成有序的链表

实现有序链表的方法是在向链表中添加节点时，按照一定的规则将它们放置在正确的位置上，使得整个链表都是有序的。以下是C语言将一个无序链表变成有序的链表的示例代码：

#include <stdio.h>
#include <stdlib.h>

/* 定义链表节点数据结构 */
typedef struct node {
    int data;
    struct node *next;
} Node;

/* 新增链表节点 */
Node *create_node(int data) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

/* 插入节点到有序链表 */
void insert_node(Node **head_ref, Node *new_node) {
    Node *current;
    /* 将新节点插入到头节点之前 */
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data) {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    /* 遍历有序链表，寻找新节点合适的插入位置 */
    else {
        current = *head_ref;
        while (current->next != NULL && current->next->data < new_node->data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

/* 将无序链表转换为有序链表 */
void convert_to_sorted_list(Node **head_ref) {
    Node *sorted_list = NULL; // 有序链表头节点
    Node *current, *next_node;
    current = *head_ref;
    while (current != NULL) {
        next_node = current->next; // 保存当前节点的下一个节点
        insert_node(&sorted_list, current); // 将当前节点插入到有序链表中
        current = next_node; // 指向下一个节点
    }
    *head_ref = sorted_list; // 更新头节点为有序链表的头节点
}

/* 输出链表节点 */
void print_list(Node *node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

/* 测试 */
int main() {
    Node *head = create_node(5);
    head->next = create_node(3);
    head->next->next = create_node(8);
    head->next->next->next = create_node(1);
    printf("The original list is: ");
    print_list(head);
    convert_to_sorted_list(&head);
    printf("The sorted list is: ");
    print_list(head);
    return 0;
}

在上述代码中，insert_node函数用于将新节点按照数据大小顺序插入到有序链表中。convert_to_sorted_list函数遍历无序链表，将每个节点插入到有序链表中，从而得到一个有序链表。最后调用print_list函数输出有序链表的每个节点数据，即所需的结果。