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

可以通过插入排序来将一个无序链表变成有序的链表。

具体实现过程如下：

1. 定义一个新的有序链表，初始值为空。

2. 遍历无序链表，取出每个节点。

3. 将当前节点插入到有序链表中的合适位置。

4. 重复步骤2-3直到遍历完整个无序链表。

5. 返回新的有序链表。

代码实现如下：

#include <stdlib.h>

/* 定义链表节点 */
typedef struct ListNode {
    int val;               // 值
    struct ListNode *next; // 指向下一个节点的指针
} ListNode;

/* 将无序链表变成有序链表 */
ListNode* sortList(ListNode* head) {
    /* 定义两个链表：有序链表和无序链表 */
    ListNode* sortedList = NULL; // 有序链表
    ListNode* unsortedList = head; // 无序链表

    while (unsortedList != NULL) {
        /* 取出当前无序链表的第一个节点 */
        ListNode* node = unsortedList;
        unsortedList = unsortedList->next;

        /* 在有序链表中查找合适的位置 */
        ListNode* prev = NULL;
        ListNode* curr = sortedList;
        while (curr != NULL && node->val > curr->val) {
            prev = curr;
            curr = curr->next;
        }

        /* 将节点插入到有序链表中的合适位置 */
        node->next = curr;
        if (prev == NULL) {
            sortedList = node;
        } else {
            prev->next = node;
        }
    }

    /* 返回新的有序链表 */
    return sortedList;
}