c++ qsort如何处理链表排序-乐工具技术知识

在C++中，要对链表进行排序，可以使用自定义比较函数作为qsort的参数。以下是一个使用qsort对链表进行排序的示例：

首先，定义一个链表节点结构体：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

然后，实现一个自定义比较函数，用于比较两个链表节点的值：

bool compare(ListNode *a, ListNode *b) {
    return a->val < b->val;
}

接下来，编写一个函数，用于将链表转换为数组，以便使用qsort进行排序：

int* linkedListToArray(ListNode *head, int &size) {
    size = 0;
    ListNode *current = head;
    while (current != NULL) {
        size++;
        current = current->next;
    }

    int *arr = new int[size];
    current = head;
    for (int i = 0; i < size; i++) {
        arr[i] = current->val;
        current = current->next;
    }

    return arr;
}

最后，编写一个函数，用于释放链表占用的内存：

void freeList(ListNode *head) {
    ListNode *current = head;
    while (current != NULL) {
        ListNode *next = current->next;
        delete current;
        current = next;
    }
}

现在，你可以使用qsort对链表进行排序了：

int main() {
    // 创建一个链表：1 -> 3 -> 2 -> 5 -> 4
    ListNode *head = new ListNode(1);
    head->next = new ListNode(3);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(5);
    head->next->next->next->next = new ListNode(4);

    int size;
    int *arr = linkedListToArray(head, size);

    // 使用qsort对数组进行排序
    qsort(arr, size, sizeof(int), compare);

    // 将排序后的数组转换回链表
    head = NULL;
    for (int i = 0; i < size; i++) {
        ListNode *newNode = new ListNode(arr[i]);
        newNode->next = head;
        head = newNode;
    }

    // 打印排序后的链表：1 -> 2 -> 3 -> 4 -> 5
    ListNode *current = head;
    while (current != NULL) {
        cout << current->val << " -> ";
        current = current->next;
    }
    cout << "NULL" << endl;

    // 释放链表占用的内存
    freeList(head);

    return 0;
}

这个示例中，我们首先创建了一个链表，然后将其转换为数组并使用qsort进行排序。最后，我们将排序后的数组转换回链表并打印结果。