C++ 代码实现链表的快速排序

链表的快速排序可以使用递归来实现。以下是一个使用C语言实现链表快速排序的示例代码：

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

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

// 交换两个节点的值
void swap(struct ListNode* a, struct ListNode* b) {
    int temp = a->val;
    a->val = b->val;
    b->val = temp;
}

// 将链表分割为两部分，返回后一部分的头节点
struct ListNode* partition(struct ListNode* start, struct ListNode* end) {
    int pivot = start->val;
    struct ListNode* p = start;
    struct ListNode* q = start->next;
    
    while (q != end) {
        if (q->val < pivot) {
            p = p->next;
            swap(p, q);
        }
        q = q->next;
    }
    
    swap(start, p);
    return p;
}

// 对链表进行快速排序
void quickSort(struct ListNode* start, struct ListNode* end) {
    if (start != end && start->next != end) {
        struct ListNode* pivot = partition(start, end);
        quickSort(start, pivot);
        quickSort(pivot->next, end);
    }
}

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

int main() {
    // 创建链表
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    
    head->val = 4;
    node2->val = 2;
    node3->val = 1;
    node4->val = 3;
    
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;
    
    printf("Before sorting: ");
    printList(head);
    
    // 进行快速排序
    quickSort(head, NULL);
    
    printf("After sorting: ");
    printList(head);
    
    // 释放链表内存
    free(head);
    free(node2);
    free(node3);
    free(node4);
    
    return 0;
}

在以上示例代码中，我们使用了递归的方式对链表进行快速排序。首先定义了链表节点的结构体 `ListNode`，其中包含了节点值 `val` 和指向下一个节点的指针 `next`。

然后，我们实现了三个辅助函数：

- `swap`：用于交换两个节点的值。
- `partition`：用于将链表分割为两部分，返回后一部分的头节点，并将链表按照基准值（pivot）进行划分。
- `quickSort`：用于递归地对链表进行快速排序。

最后，在 `main` 函数中，我们创建了一个包含四个节点的链表，并打印排序前后的链表。注意，在程序结束时，需要释放链表节点所占用的内存。

希望对你有所帮助！如果有任何疑问，请随时提问。