快速排序对链表进行排序c语言

快速排序是一种非常高效的排序算法，对于链表的排序也可以采用快速排序算法。

C 语言实现代码如下：

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

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

// 快速排序函数
struct ListNode* quickSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 将链表分为两个部分
    struct ListNode *left = head, *right = head->next;
    while (right != NULL) {
        if (right->val < head->val) {
            left = left->next;
            int temp = left->val;
            left->val = right->val;
            right->val = temp;
        }
        right = right->next;
    }
    int temp = head->val;
    head->val = left->val;
    left->val = temp;

    // 递归排序
    head->next = quickSortList(head->next);
    left->next = quickSortList(left->next);

    return head;
}

// 创建链表
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 = quickSortList(head);
    printf("Sorted list: ");
    printList(head);

    return 0;
}

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

我们使用 `quickSortList` 函数对链表进行快速排序。在函数中，我们首先确定链表的中心节点 `head`，然后将链表分为两个部分：左侧节点值小于中心节点值，右侧节点值大于中心节点值。我们通过交换节点值的方式将节点分为两个部分。

接下来，我们递归对左侧链表和右侧链表进行排序，然后将两个链表合并起来。

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