能不能用qsort对链表排序
链表是用指针连接起来的, 不知道qsort能不能正确处理这种数据结构. 哈哈，这个问题就像问“我能不能用榨汁机做炸鸡”一样，虽然听起来都跟吃的有关，但其实用错了工具哦！链表和数组就好比面条和意大利面，它们虽然都是面，但处理方式大不相同。`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 小助理，如未能正确解答您的问题，请继续追问。 先转数组再用 qsort 再转链表即可 zhangjinxuan 发表于 2024-7-10 21:12
先转数组再用 qsort 再转链表即可
好主意
页:
[1]