网站名称写什么,网易邮箱163登录入口,如何用网站做淘客,标志设计公司成都为了对给定的单链表按升序排序#xff0c;我们可以考虑以下解决方法#xff1a;
思路 归并排序#xff08;Merge Sort#xff09;#xff1a;由于归并排序的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)#xff0c;并且归并排序不需要额外的空间#xff08;空…为了对给定的单链表按升序排序我们可以考虑以下解决方法
思路 归并排序Merge Sort由于归并排序的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)并且归并排序不需要额外的空间空间复杂度为 O ( 1 ) O(1) O(1)但实际上需要递归栈空间这使得它非常适合用来排序链表。通过归并排序对链表进行排序时节点的值会被有效地排序同时还保证了时间和空间的复杂度要求。 链表操作我们需要将链表分割为两个子链表递归地对这两个子链表进行排序然后合并它们。
步骤
分割链表通过快慢指针的方法找到链表的中间节点将链表分为两部分。递归排序递归地对每一部分链表进行排序。合并排序后的链表将两个已排序的链表合并成一个有序链表。
代码实现
struct ListNode {int val;struct ListNode* next;
};/*** 合并两个已经排序的链表*/
#include stdio.h
#include stdlib.hstruct ListNode {int val;struct ListNode* next;
};/*** 合并两个已经排序的链表*/
struct ListNode* merge(struct ListNode* left, struct ListNode* right) {struct ListNode dummy;struct ListNode* p dummy;// 合并两个链表while (left ! NULL right ! NULL) {if (left-val right-val) {p-next left;left left-next;} else {p-next right;right right-next;}p p-next;}// 如果还有剩余的元素直接连接到结果链表if (left ! NULL) {p-next left;} else {p-next right;}return dummy.next;
}/*** 找到链表的中间节点*/
struct ListNode* findMid(struct ListNode* head) {// 添加空指针检查if (head NULL || head-next NULL) {return head;}struct ListNode* slow head;struct ListNode* fast head-next; // Changed initial position// 快慢指针找到中点while (fast ! NULL fast-next ! NULL) {slow slow-next;fast fast-next-next;}return slow;
}/*** 归并排序链表*/
struct ListNode* sortInList(struct ListNode* head) {// 如果链表为空或只有一个元素直接返回if (head NULL || head-next NULL)return head;// 找到链表的中间节点struct ListNode* mid findMid(head);struct ListNode* right mid-next;mid-next NULL; // 分割链表为两部分struct ListNode* left head;// 递归排序两个子链表left sortInList(left);right sortInList(right);// 合并两个排序后的链表return merge(left, right);
}int main() { // Changed from void main() to int main()// 创建链表: 1 - 2 - 3 - 4 - 5struct ListNode* pHead1 (struct ListNode*)malloc(sizeof(struct ListNode));pHead1-val 1;pHead1-next (struct ListNode*)malloc(sizeof(struct ListNode));pHead1-next-val 2;pHead1-next-next (struct ListNode*)malloc(sizeof(struct ListNode));pHead1-next-next-val 3;pHead1-next-next-next (struct ListNode*)malloc(sizeof(struct ListNode));pHead1-next-next-next-val 4;pHead1-next-next-next-next (struct ListNode*)malloc(sizeof(struct ListNode));pHead1-next-next-next-next-val 5;pHead1-next-next-next-next-next NULL;// 排序链表struct ListNode* result sortInList(pHead1);// 打印排序后的链表struct ListNode* cur result;while (cur ! NULL) {printf(%d - , cur-val);cur cur-next;}printf(NULL\n);// 释放内存while (result ! NULL) {struct ListNode* temp result;result result-next;free(temp);}return 0;
}补充选择 dummy.next 或 dummy-next
在代码中dummy.next 和 dummy-next 之间的区别取决于你使用的指针类型和编程语言的语法。
区别 dummy.next这种写法通常用于在结构体中定义成员变量的情况这种写法适用于对象实例而非指针类型。例如 struct ListNode {int val;ListNode* next; // 这是一个指针成员变量
};ListNode dummy;
dummy.next someNode; // 直接访问dummy对象的next成员dummy-next这种写法通常用于通过指针访问结构体的成员。在这种情况下dummy 是指向结构体的指针你需要使用箭头操作符 - 来访问结构体的成员变量。例如 ListNode* dummy new ListNode();
dummy-next someNode; // 使用箭头符号来访问指针dummy的next成员选择 dummy.next 或 dummy-next
dummy.next 是用在我们直接创建一个结构体对象时即没有使用指针通过对象访问其成员变量。dummy-next 是用在我们使用结构体指针时通过指针来访问结构体的成员变量。
代码中的具体情况
在你的归并排序代码中dummy 是一个结构体对象而不是指针所以我们使用 dummy.next 来访问结构体成员 next。而如果我们把 dummy 定义为一个指针即 ListNode* dummy new ListNode();那么就应该使用 dummy-next 来访问成员变量。
举个例子
使用结构体对象时
ListNode dummy;
dummy.next someNode; // 直接通过对象访问使用结构体指针时
ListNode* dummy new ListNode();
dummy-next someNode; // 使用箭头符号访问成员总结
dummy.next适用于 dummy 是结构体对象的情况。dummy-next适用于 dummy 是结构体指针的情况。 还是挺好理解的如果定义的是一个结构体用.如果定义的是一个结构体指针用的是-。
解释
merge 函数将两个已排序的链表合并成一个排序好的链表。我们通过逐个比较节点的值来合并。findMiddle 函数使用快慢指针来找到链表的中间节点。快指针每次移动两步慢指针每次移动一步。当快指针到达链表末尾时慢指针刚好到达中间位置。sortInList 函数这是主要的排序函数利用归并排序的思想。首先通过 findMiddle 找到中间节点将链表分为两部分然后递归地对每一部分链表进行排序最后用 merge 将排序后的两部分合并。
时间复杂度
归并排序的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)其中 n n n 是链表的节点数。每次递归分割链表的时间复杂度为 O ( n ) O(n) O(n)总共递归的层数为 O ( log n ) O(\log n) O(logn)因此总的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
空间复杂度
归并排序的空间复杂度为 O ( n ) O(n) O(n)因为递归栈的空间复杂度是 O ( log n ) O(\log n) O(logn)但每次合并需要额外的空间来存储结果链表。
