插入排序对链表进行排序c语言

插入排序也是一种简单有效的排序算法，对于链表的排序也可以采用插入排序算法。

C 语言实现代码如下：

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

// 链表节点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

// 插入排序函数
struct ListNode* insertionSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *newHead = (struct ListNode *)malloc(sizeof(struct ListNode));
    newHead->val = -1;
    newHead->next = head;

    struct ListNode *cur = head->next, *pre = head;
    while (cur != NULL) {
        if (cur->val >= pre->val) {
            pre = cur;
            cur = cur->next;
        } else {
            struct ListNode *p = newHead;
            while (p->next->val < cur->val) {
                p = p->next;
            }
            pre->next = cur->next;
            cur->next = p->next;
            p->next = cur;
            cur = pre->next;
        }
    }

    return newHead->next;
}

// 创建链表
struct ListNode* createList(int arr[], int n) {
    struct ListNode *head = NULL, *cur = NULL;
    for (int i = 0; i < n; i++) {
        struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
        node->val = arr[i];
        node->next = NULL;
        if (head == NULL) {
            head = node;
        } else {
            cur->next = node;
        }
        cur = node;
    }
    return head;
}

// 打印链表
void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 1, 3};
    int n = sizeof(arr) / sizeof(int);
    struct ListNode *head = createList(arr, n);
    printf("Original list: ");
    printList(head);

    head = insertionSortList(head);
    printf("Sorted list: ");
    printList(head);

    return 0;
}

在这个代码中，我们定义了一个 `ListNode` 结构体表示链表节点，其中包含一个 `val` 字段和一个 `next` 指针指向下一个节点。

我们使用 `insertionSortList` 函数对链表进行插入排序。在函数中，我们首先创建一个新的头节点 `newHead`，将其值设为 `-1`，将其 `next` 指向原链表的头节点 `head`。

接下来，我们使用两个指针 `pre` 和 `cur` 分别指向已排序部分的末尾节点和未排序部分的头节点。如果 `cur` 的值大于等于 `pre` 的值，则将 `pre` 和 `cur` 向后移动一个节点；否则，我们需要将 `cur` 插入到已排序部分中。

为了找到 `cur` 应该插入的位置，我们使用一个指针 `p` 遍历已排序部分。如果 `p->next->val` 小于 `cur->val`，则将 `p` 向后移动一个节点；否则，我们将 `cur` 插入到 `p` 后面。

最后，我们返回 `newHead->next`，即为排序后的链表。

通过 `createList` 函数创建链表，并通过 `printList` 函数打印链表。