题目描述给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3]输出[1,2,3,4]示例 2输入head [-1,5,3,4,0]输出[-1,0,3,4,5]示例 3输入head []输出[]解题思路方法一辅助数组法我的思路先把链表的值存入 vector排序再重建链表。具体步骤边界处理空链表直接返回取值遍历链表把所有值存入temp排序用sort对temp排序重建用排序后的值新建链表节点连接成新链表返回返回新链表头节点用例子走一遍head 4 - 2 - 1 - 3步骤操作结果1遍历链表temp [4, 2, 1, 3]2排序temp [1, 2, 3, 4]3重建链表1 - 2 - 3 - 44返回1 - 2 - 3 - 4✅复杂度分析维度复杂度说明时间复杂度O(n log n)遍历 O(n) 排序 O(n log n) 重建 O(n)空间复杂度O(n)vector 存储 n 个值 新建 n 个节点时间复杂度已经是最优的排序下界就是 O(n log n)但空间复杂度不是最优。缺点❌空间复杂度 O(n)需要额外存储所有值和新建所有节点❌没有利用链表的特性链表题应该用指针操作而不是转成数组和最优解法的对比对比维度方法一最优解法归并排序时间复杂度O(n log n)O(n log n)空间复杂度O(n)O(log n)递归栈或 O(1)迭代是否新建节点✅ 需要❌ 不需要是否修改原链表❌ 不修改✅ 修改面试推荐度⭐⭐⭐⭐⭐⭐⭐⭐方法二归并排序最优解法为什么用归并排序排序算法数组链表快速排序✅ 常用❌ 需要随机访问归并排序✅ 常用✅最适合链表堆排序✅ 常用❌ 需要随机访问归并排序最适合链表因为链表不支持随机访问快排需要随机访问归并排序只需要顺序访问合并两个有序链表是 O(1) 空间操作核心思路1. 快慢指针找中点把链表分成两半 2. 递归排序左半部分 3. 递归排序右半部分 4. 合并两个有序链表代码实现class Solution { public: ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) return head; // 第1步快慢指针找中点 ListNode *slow head, *fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } ListNode *mid slow-next; slow-next nullptr; // 断开链表 // 第2步递归排序左右两半 ListNode *left sortList(head); ListNode *right sortList(mid); // 第3步合并两个有序链表 return merge(left, right); } private: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode *dummy new ListNode(0); ListNode *curr dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { curr-next l1; l1 l1-next; } else { curr-next l2; l2 l2-next; } curr curr-next; } curr-next (l1 ! nullptr) ? l1 : l2; return dummy-next; } };复杂度分析维度复杂度时间复杂度O(n log n)空间复杂度O(log n)递归栈深度方法三自底向上归并排序O(1) 空间class Solution { public: ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) return head; // 求链表长度 int len 0; ListNode* p head; while (p ! nullptr) { len; p p-next; } ListNode* dummy new ListNode(0); dummy-next head; // 自底向上归并 for (int size 1; size len; size * 2) { ListNode *prev dummy, *curr dummy-next; while (curr ! nullptr) { ListNode *left curr; ListNode *right split(left, size); curr split(right, size); prev merge(left, right, prev); } } return dummy-next; } private: // 从 head 开始切下 size 个节点返回剩余部分的头 ListNode* split(ListNode* head, int size) { if (head nullptr) return nullptr; for (int i 1; i size head-next ! nullptr; i) { head head-next; } ListNode* rest head-next; head-next nullptr; return rest; } // 合并两个有序链表接到 prev 后面 ListNode* merge(ListNode* l1, ListNode* l2, ListNode* prev) { ListNode* curr prev; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { curr-next l1; l1 l1-next; } else { curr-next l2; l2 l2-next; } curr curr-next; } curr-next (l1 ! nullptr) ? l1 : l2; while (curr-next ! nullptr) { curr curr-next; } return curr; } };复杂度时间 O(n log n)空间O(1)三种方法对比方法时间复杂度空间复杂度是否新建节点推荐度辅助数组法O(n log n)O(n)✅ 需要⭐⭐⭐归并排序递归O(n log n)O(log n)❌ 不需要⭐⭐⭐⭐⭐归并排序迭代O(n log n)O(1)❌ 不需要⭐⭐⭐⭐