每日一题-单链表排序

为了对给定的单链表按升序排序，我们可以考虑以下解决方法：

思路

1. 归并排序（Merge Sort）：由于归并排序的时间复杂度为 $O(n\log n)$，并且归并排序不需要额外的空间（空间复杂度为 $O(1)$，但实际上需要递归栈空间），这使得它非常适合用来排序链表。通过归并排序对链表进行排序时，节点的值会被有效地排序，同时还保证了时间和空间的复杂度要求。

2. 链表操作：我们需要将链表分割为两个子链表，递归地对这两个子链表进行排序，然后合并它们。

步骤

1. 分割链表：通过快慢指针的方法找到链表的中间节点，将链表分为两部分。
2. 递归排序：递归地对每一部分链表进行排序。
3. 合并排序后的链表：将两个已排序的链表合并成一个有序链表。

代码实现

struct ListNode {int val;struct ListNode* next;
};/*** 合并两个已经排序的链表*/
#include <stdio.h>
#include <stdlib.h>struct 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 之间的区别取决于你使用的指针类型和编程语言的语法。

区别

1. dummy.next：这种写法通常用于在结构体中定义成员变量的情况，这种写法适用于对象实例而非指针类型。例如：

   struct ListNode {int val;ListNode* next;  // 这是一个指针成员变量
   };ListNode dummy;
   dummy.next = someNode;  // 直接访问dummy对象的next成员
   

2. 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 是结构体指针的情况。
  还是挺好理解的，如果定义的是一个结构体，用.，如果定义的是一个结构体指针，用的是->。

解释

1. merge 函数：将两个已排序的链表合并成一个排序好的链表。我们通过逐个比较节点的值来合并。
2. findMiddle 函数：使用快慢指针来找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针刚好到达中间位置。
3. sortInList 函数：这是主要的排序函数，利用归并排序的思想。首先通过 findMiddle 找到中间节点，将链表分为两部分，然后递归地对每一部分链表进行排序，最后用 merge 将排序后的两部分合并。

时间复杂度

• 归并排序的时间复杂度为 $O(n\log n)$，其中 $n$ 是链表的节点数。
• 每次递归分割链表的时间复杂度为 $O(n)$，总共递归的层数为 $O(\log n)$，因此总的时间复杂度为 $O(n\log n)$。

空间复杂度

• 归并排序的空间复杂度为 $O(n)$，因为递归栈的空间复杂度是 $O(\log n)$，但每次合并需要额外的空间来存储结果链表。