C语言链表如何根据节点值的大小重新将链表排序

要根据节点值的大小重新排序链表，可以使用插入排序或归并排序算法。

插入排序的基本思想是将未排序的元素插入到已排序的元素中。具体实现时，可以维护一个有序的链表，然后遍历未排序的节点，将它们插入到有序的链表中。插入节点时，需要找到它应该插入的位置，然后将它插入到链表中。

归并排序的基本思想是将一个大问题拆分成多个小问题，然后将小问题逐个解决，最终合并成一个解决了大问题。具体实现时，可以将链表拆分成两个子链表，然后对子链表进行排序，最后将两个有序的子链表合并成一个有序的链表。

下面是一个使用插入排序实现链表排序的示例代码：

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

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

void printList(Node *head) {
    Node *p = head;
    while(p != NULL) {
        printf("%d ", p->value);
        p = p->next;
    }
    printf("\n");
}

void insert(Node **head, Node *node) {
    if(*head == NULL || (*head)->value >= node->value) {
        node->next = *head;
        *head = node;
    } else {
        Node *p = *head;
        while(p->next != NULL && p->next->value < node->value) {
            p = p->next;
        }
        node->next = p->next;
        p->next = node;
    }
}

void sortList(Node **head) {
    Node *sorted = NULL;
    Node *p = *head;
    while(p != NULL) {
        Node *next = p->next;
        insert(&sorted, p);
        p = next;
    }
    *head = sorted;
}

int main() {
    Node *head = NULL;
    Node *node1 = (Node *)malloc(sizeof(Node));
    node1->value = 3;
    node1->next = NULL;

    Node *node2 = (Node *)malloc(sizeof(Node));
    node2->value = 1;
    node2->next = NULL;

    Node *node3 = (Node *)malloc(sizeof(Node));
    node3->value = 2;
    node3->next = NULL;

    head = node1;
    node1->next = node2;
    node2->next = node3;

    printf("Before sorting: ");
    printList(head);

    sortList(&head);

    printf("After sorting: ");
    printList(head);

    return 0;
}

这个示例代码中，`insert()` 函数用于将一个节点插入到已排序的链表中。 `sortList()` 函数则遍历未排序的节点，将它们插入到已排序的链表中，最终得到一个有序的链表。

这是一个使用归并排序实现链表排序的示例代码：

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

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

void printList(Node *head) {
    Node *p = head;
    while(p != NULL) {
        printf("%d ", p->value);
        p = p->next;
    }
    printf("\n");
}

void splitList(Node *head, Node **left, Node **right) {
    Node *fast = head;
    Node *slow = head;
    while(fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    *left = head;
    *right = slow->next;
    slow->next = NULL;
}

Node *mergeLists(Node *left, Node *right) {
    if(left == NULL) return right;
    if(right == NULL) return left;
    Node *head = NULL;
    if(left->value <= right->value) {
        head = left;
        head->next = mergeLists(left->next, right);
    } else {
        head = right;
        head->next = mergeLists(left, right->next);
    }
    return head;
}

void sortList(Node **head) {
    if(*head == NULL || (*head)->next == NULL) return;
    Node *left = NULL;
    Node *right = NULL;
    splitList(*head, &left, &right);
    sortList(&left);
    sortList(&right);
    *head = mergeLists(left, right);
}

int main() {
    Node *head = NULL;
    Node *node1 = (Node *)malloc(sizeof(Node));
    node1->value = 3;
    node1->next = NULL;

    Node *node2 = (Node *)malloc(sizeof(Node));
    node2->value = 1;
    node2->next = NULL;

    Node *node3 = (Node *)malloc(sizeof(Node));
    node3->value = 2;
    node3->next = NULL;

    head = node1;
    node1->next = node2;
    node2->next = node3;

    printf("Before sorting: ");
    printList(head);

    sortList(&head);

    printf("After sorting: ");
    printList(head);

    return 0;
}

这个示例代码中，`splitList()` 函数将链表拆分成两个子链表。`mergeLists()` 函数则将两个有序的子链表合并成一个有序的链表。`sortList()` 函数则将链表拆分成两个子链表，然后对每个子链表进行排序，最后将两个有序的子链表合并成一个有序的链表。