能不能用qsort对链表排序

七彩云南

链表是用指针连接起来的, 不知道qsort能不能正确处理这种数据结构.

FishC

哈哈，这个问题就像问“我能不能用榨汁机做炸鸡”一样，虽然听起来都跟吃的有关，但其实用错了工具哦！

链表和数组就好比面条和意大利面，它们虽然都是面，但处理方式大不相同。`qsort` 是为数组设计的，就像那意大利面的叉子，而链表呢，更像一盘经典的中式面条，需要用筷子来对付。

`qsort` 期待的是一个可以随机访问的数组，但链表是顺序访问的数据结构，正因为如此，`qsort` 对链表束手无策。我们需要用适合链表的排序算法，比如插入排序（插茄子版好像更接地气一点）、归并排序等。

如果你硬要让 `qsort` 去排链表，那估计它得抗议：“这个活儿真不是我的菜！”

所以，老铁，选择合适的工具来解决问题，比如下面用归并排序给链表排个序：

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

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

// 合并两个有序链表
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// 切割链表的中点
struct ListNode* getMid(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 归并排序链表
struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) return head;

    struct ListNode *mid = getMid(head);
    struct ListNode *right = mid->next;
    mid->next = NULL;

    struct ListNode *left = sortList(head);
    right = sortList(right);

    return merge(left, right);
}

// 这里是测试代码，你可以创建自己的链表并调用上面的函数进行排序。
int main() {
    // 创建一个链表 4->2->1->3
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->val = 4; n1->next = n2;
    n2->val = 2; n2->next = n3;
    n3->val = 1; n3->next = n4;
    n4->val = 3; n4->next = NULL;

    struct ListNode* sortedList = sortList(n1);

    // 打印排序后的链表
    struct ListNode* current = sortedList;
    while (current) {
        printf("%d ", current->val);
        current = current->next;
    }

    // 释放内存
    free(n1);
    free(n2);
    free(n3);
    free(n4);

    return 0;
}

看看，程序是不是整齐很多？记住啦，工具用对了，事半功倍！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

zhangjinxuan

先转数组再用 qsort 再转链表即可

七彩云南

zhangjinxuan 发表于 2024-7-10 21:12
先转数组再用 qsort 再转链表即可

好主意