1 排序链表

1.1 插入法 O（n²）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {O（n²）超出时间限制if(!head||!head->next) return head;ListNode* sorted = nullptr; // 维护一个新链表ListNode* node = head;while (node){ListNode* nextNode = node->next; // 记录下一个要处理的节点// 在有序链表中找到正确的位置插入 nodeif(!sorted||node->val<=sorted->val){node->next = sorted;sorted = node;}else{ListNode* find = sorted;while (find->next && find->next->val < node->val) {find = find->next;}node->next=find->next;find->next=node;}node=nextNode;}return sorted;}
};

1.2 归并排序

✅ 时间复杂度降至 O(n log n)
✅ 快慢指针找中点，避免遍历两次
✅ 递归拆分 + 归并合并，代码简洁易读
✅ 使用 dummy 头节点合并链表，避免特殊处理

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* merge(ListNode* left,ListNode* right){if(!left) return right;if(!right) return left;ListNode dummy(0);ListNode *cur=&dummy;while(left&&right){if(left->val<right->val){cur->next=left;left=left->next;}else{cur->next=right;right=right->next;}cur = cur->next;}if(left){cur->next=left;}if(right){cur->next=right;}return dummy.next;}ListNode* sortList(ListNode* head) {// 方法二归并排序// 首先快慢指针找到中心if(!head||!head->next) return head;ListNode*slow=head,*fast=head,*pre=nullptr;while(fast&&fast->next){pre =  slow;slow=slow->next;fast=fast->next->next;}pre->next = nullptr; // 断开链表// 2. 递归排序左右两部分ListNode* left = sortList(head);ListNode* right = sortList(slow);return merge(left,right);}
};