写一份C语言带表头结点单链表的排序函数代码

在C语言中，我们可以使用内置的qsort函数对一个带头结点的单链表进行排序。以下是一个简单的示例，假设我们有一个结构体`ListNode`表示链表节点，其中包含一个整数值`val`和指向下一个节点的指针`next`：

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

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

void swapNodes(ListNode** a, ListNode** b) {
    ListNode temp = *a;
    *a = *b;
    *b = temp;
}

// 快速排序算法的核心部分
int partition(ListNode** head, ListNode** pivot) {
    ListNode* less = *head;
    ListNode* equal = *pivot;
    ListNode* greater = NULL;

    while (equal->next != NULL) {
        if (equal->val < equal->next->val) {
            less = less->next;
        } else {
            if (greater == NULL) {
                greater = equal->next;
                equal->next = NULL;
            } else {
                ListNode* tail = greater;
                tail->next = equal->next;
                equal->next = NULL;
                tail = tail->next;
            }
        }
    }

    if (less == *head) {
        return equal->val; // 如果pivot是第一个元素，则交换其位置
    } else {
        ListNode* tail = greater;
        while (tail != NULL) {
            equal->next = tail;
            equal = equal->next;
            tail = tail->next;
        }
        equal->next = NULL;
        return less->val;
    }
}

// 带头结点的单链表排序函数
void sortList(ListNode** head) {
    if (*head == NULL || (*head)->next == NULL) {
        return; // 特殊情况：空链表或只有一个元素
    }

    ListNode* pivot = *head;
    ListNode* left = *head;
    ListNode* right = pivot->next;

    while (right != NULL) {
        ListNode* pivotNew = partition(&left, &right);
        if (pivotNew == pivot->val) {
            pivot = pivot->next;
        } else if (pivotNew < pivot->val) {
            pivot = pivot->next;
            left = pivot;
        } else {
            right = pivotNew->next;
        }
    }

    *head = pivot; // 将排序后的链表首部移到正确的位置
}

// 示例用法
void printList(ListNode* head) {
    while (head != NULL) {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // 创建并初始化一个链表
    ListNode* list = malloc(sizeof(ListNode));
    list->val = 5;
    list->next = malloc(sizeof(ListNode));
    list->next->val = 2;
    list->next->next = malloc(sizeof(ListNode));
    list->next->next->val = 8;
    list->next->next->next = malloc(sizeof(ListNode));
    list->next->next->next->val = 1;
    list->next->next->next->next = NULL;

    printf("Original List: ");
    printList(list);

    sortList(&list);

    printf("\nSorted List: ");
    printList(list);

    free(list);
    return 0;
}

这个代码实现了快速排序算法对单链表进行排序，但请注意快速排序在实际应用时可能不适合链表，因为它需要前后节点的直接访问，而链表操作通常是逐个节点进行的。对于链表，更常见的方法可能是归并排序，它的遍历过程不会导致额外的内存消耗。