链表选择排序法c语言

链表选择排序是一种常见的排序算法，用于对链表中的元素进行排序。下面是链表选择排序的C语言实现：

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

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

// 创建新节点
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 释放链表内存
void freeList(struct ListNode* head) {
    struct ListNode* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// 找到链表中最小值节点的前一个节点
struct ListNode* findMinPrev(struct ListNode* head) {
    struct ListNode* minPrev = NULL;
    struct ListNode* minNode = head;
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;

    while (curr != NULL && curr->next != NULL) {
        if (curr->next->val < minNode->val) {
            minPrev = curr;
            minNode = curr->next;
        }
        curr = curr->next;
    }

    return minPrev;
}

// 链表选择排序
struct ListNode* selectionSort(struct ListNode* head) {
    struct ListNode* sortedHead = NULL;
    struct ListNode* sortedTail = NULL;

    while (head != NULL) {
        struct ListNode* minPrev = findMinPrev(head);
        if (minPrev == NULL) {
            // 当前节点是最小值节点
            struct ListNode* nextNode = head->next;
            if (sortedHead == NULL) {
                sortedHead = head;
                sortedTail = head;
            } else {
                sortedTail->next = head;
                sortedTail = head;
            }
            head->next = NULL;
            head = nextNode;
        } else {
            // 当前节点不是最小值节点
            struct ListNode* minNode = minPrev->next;
            minPrev->next = minNode->next;
            if (sortedHead == NULL) {
                sortedHead = minNode;
                sortedTail = minNode;
            } else {
                sortedTail->next = minNode;
                sortedTail = minNode;
            }
            minNode->next = NULL;
        }
    }

    return sortedHead;
}

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

int main() {
    // 创建链表
    struct ListNode* head = createNode(4);
    head->next = createNode(2);
    head->next->next = createNode(1);
    head->next->next->next = createNode(3);

    printf("原始链表：");
    printList(head);

    // 链表选择排序
    struct ListNode* sortedHead = selectionSort(head);

    printf("排序后链表：");
    printList(sortedHead);

    // 释放链表内存
    freeList(sortedHead);

    return 0;
}

以上是链表选择排序的C语言实现。首先，我们定义了一个链表节点的结构体`ListNode`，包含一个整数值`val`和指向下一个节点的指针`next`。然后，我们实现了创建新节点的函数`createNode`和释放链表内存的函数`freeList`。

接下来，我们实现了找到链表中最小值节点的前一个节点的函数`findMinPrev`。该函数用于在链表中找到最小值节点，并返回其前一个节点的指针。

然后，我们实现了链表选择排序的函数`selectionSort`。该函数使用循环遍历链表，每次找到最小值节点并将其移动到已排序部分的末尾。

最后，在`main`函数中，我们创建了一个示例链表，并调用`selectionSort`函数对其进行排序。然后，打印原始链表和排序后的链表，并释放链表内存。