能不能用qsort对链表排序

七彩云南

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

FishC

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

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

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

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

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. // 定义链表节点
   
5. struct ListNode {
   
6.     int val;
   
7.     struct ListNode *next;
   
8. };
   
9. 
   
10. // 合并两个有序链表
    
11. struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    
12.     if (!l1) return l2;
    
13.     if (!l2) return l1;
    
14. 
    
15.     if (l1->val < l2->val) {
    
16.         l1->next = merge(l1->next, l2);
    
17.         return l1;
    
18.     } else {
    
19.         l2->next = merge(l1, l2->next);
    
20.         return l2;
    
21.     }
    
22. }
    
23. 
    
24. // 切割链表的中点
    
25. struct ListNode* getMid(struct ListNode* head) {
    
26.     struct ListNode* slow = head;
    
27.     struct ListNode* fast = head->next;
    
28. 
    
29.     while (fast && fast->next) {
    
30.         slow = slow->next;
    
31.         fast = fast->next->next;
    
32.     }
    
33.     return slow;
    
34. }
    
35. 
    
36. // 归并排序链表
    
37. struct ListNode* sortList(struct ListNode* head) {
    
38.     if (!head || !head->next) return head;
    
39. 
    
40.     struct ListNode *mid = getMid(head);
    
41.     struct ListNode *right = mid->next;
    
42.     mid->next = NULL;
    
43. 
    
44.     struct ListNode *left = sortList(head);
    
45.     right = sortList(right);
    
46. 
    
47.     return merge(left, right);
    
48. }
    
49. 
    
50. // 这里是测试代码，你可以创建自己的链表并调用上面的函数进行排序。
    
51. int main() {
    
52.     // 创建一个链表 4->2->1->3
    
53.     struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    
54.     struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    
55.     struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    
56.     struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    
57. 
    
58.     n1->val = 4; n1->next = n2;
    
59.     n2->val = 2; n2->next = n3;
    
60.     n3->val = 1; n3->next = n4;
    
61.     n4->val = 3; n4->next = NULL;
    
62. 
    
63.     struct ListNode* sortedList = sortList(n1);
    
64. 
    
65.     // 打印排序后的链表
    
66.     struct ListNode* current = sortedList;
    
67.     while (current) {
    
68.         printf("%d ", current->val);
    
69.         current = current->next;
    
70.     }
    
71. 
    
72.     // 释放内存
    
73.     free(n1);
    
74.     free(n2);
    
75.     free(n3);
    
76.     free(n4);
    
77. 
    
78.     return 0;
    
79. }

复制代码

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

zhangjinxuan

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

七彩云南

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

好主意