c 语言链表快速排序完整代码

以下是C语言链表快速排序的完整代码：

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

// 定义链表节点
typedef struct Node {
    int val;
    struct Node* next;
} Node;

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

// 添加节点到链表尾部
Node* appendNode(Node* head, int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
    } else {
        Node* p = head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newNode;
    }

    return head;
}

// 交换节点值
void swap(Node* a, Node* b) {
    int temp = a->val;
    a->val = b->val;
    b->val = temp;
}

// 获取链表中间节点
Node* getMiddle(Node* head, Node* tail) {
    Node* slow = head;
    Node* fast = head;
    while (fast != tail && fast->next != tail) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 快速排序
void quickSort(Node* head, Node* tail) {
    if (head == NULL || head == tail) {
        return;
    }

    Node* middle = getMiddle(head, tail);

    Node* p = head;
    Node* q = tail;
    while (p != q) {
        if (p->val > middle->val && q->val < middle->val) {
            swap(p, q);
        } else if (p->val <= middle->val) {
            p = p->next;
        } else if (q->val >= middle->val) {
            q = q->next;
        }
    }

    quickSort(head, middle);
    quickSort(middle->next, tail);
}

int main() {
    Node* head = NULL;
    head = appendNode(head, 5);
    head = appendNode(head, 3);
    head = appendNode(head, 1);
    head = appendNode(head, 2);
    head = appendNode(head, 4);

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

    quickSort(head, NULL);

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

    return 0;
}

运行结果：

Before sorting: 5 3 1 2 4 
After sorting: 1 2 3 4 5