c语言单链表快速排序

以下是使用C语言实现单链表快速排序的示例代码：

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

// 定义单链表结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

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

// 将节点插入到链表末尾
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 交换两个节点的数据
void swap(Node* a, Node* b) {
    int temp = a->data;
    a->data = b->data;
    b->data = temp;}

// 找到链表的中间节点
Node* getMiddle(Node* head, Node* end) {
    if (head == NULL) {
        return head;
    }
    Node* slow = head;
    Node* fast = head->next;
    while (fast != end) {
        fast = fast->next;
        if (fast != end) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    return slow;
}

// 快速排序的递归函数
void quickSortUtil(Node* head, Node* end) {
    if (head == end || head->next == end) {
        return;
    }
    Node* pivotPrev = getMiddle(head, end);
    Node* pivot = pivotPrev->next;
    Node* curr = pivot->next;
    Node* tail = end;
    while (curr != tail) {
        if (curr->data < pivot->data) {
            swap(curr, head->next);
            head = head->next;
        } else {
            curr = curr->next;
        }
    }
    swap(pivot, head);
    quickSortUtil(head, pivotPrev);
    quickSortUtil(pivot->next, end);
}

// 快速排序函数
void quickSort(Node** head) {
    quickSortUtil(*head, NULL);
}

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

int main() {
    Node* head = NULL;
    insertNode(&head, 5);
    insertNode(&head, 2);
    insertNode(&head, 8);
    insertNode(&head, 1);
    insertNode(&head, 6);

    printf("排序前的链表：");
    printList(head);

    quickSort(&head);

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

    return 0;
}