一、题目核心解析1. 题目要求给定单链表的头节点head将链表按升序排列并返回排序后的链表。输入示例head [4,2,1,3]→ 输出[1,2,3,4]数据范围链表节点数∈(0, 5×10⁴)节点值∈[-10⁵, 10⁵]进阶挑战在O (n log n) 时间、O (1) 空间内完成排序2. 算法选型分析链表的非连续存储特性直接排除了数组中高效的随机访问类排序。结合复杂度要求算法选型如下表格排序算法时间复杂度空间复杂度适配性冒泡 / 插入排序O(n²)O(1)❌ 超时无法处理大数据量快速排序平均 O (n log n)O(log n)❌ 链表随机访问开销大递归栈空间不满足进阶要求堆排序O(n log n)O(1)❌ 链表实现复杂无数组下标优势归并排序O(n log n)O(log n)/O(1)✅ 最优解完美适配链表分治与指针操作归并排序的核心优势分治思想天然适配链表分割仅需快慢指针合并仅调整指针无需额外空间是唯一能同时满足时间与空间进阶要求的算法。二、核心前置知识链表操作基石解决这道题前需掌握两个核心基础操作也是解题的 “工具包”1. 快慢指针找中点分割核心通过快慢指针将链表从中间拆分为左右两部分为分治做准备。原理慢指针slow每次走 1 步快指针fast每次走 2 步当fast到达链表尾时slow指向中点。关键细节快指针初始指向head-next确保偶数长度链表时slow指向前半段尾节点便于精准分割。2. 合并两个有序链表合并核心将两个已升序排列的链表合并为一个新的升序链表核心是双指针 虚拟头节点无需创建新节点仅调整指针指向。虚拟头节点dummy简化边界处理无需单独判断空链表统一拼接逻辑。三、解法一自顶向下递归归并清晰易上手1. 算法思路遵循分治 “分割 - 治理 - 合并” 的核心逻辑递归实现分割用快慢指针找到链表中点将链表拆分为左、右两部分治理递归排序左、右两个子链表直到子链表长度为 1天然有序合并将两个有序子链表合并为一个有序链表回溯得到最终结果。2. 完整 C 代码cpp运行/** * 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) { // 递归终止条件空链表或单节点链表天然有序 if (!head || !head-next) { return head; } // 1. 快慢指针找中点分割链表 ListNode* mid findMid(head); ListNode* rightHead mid-next; mid-next nullptr; // 切断左、右子链表避免循环引用 // 2. 递归排序左、右子链表 ListNode* leftSorted sortList(head); ListNode* rightSorted sortList(rightHead); // 3. 合并两个有序链表 return mergeTwoLists(leftSorted, rightSorted); } private: // 快慢指针找链表中点前半段尾节点 ListNode* findMid(ListNode* head) { ListNode* slow head; ListNode* fast head-next; // 关键偶数长度时指向中点前一位 while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; } // 合并两个有序链表核心工具函数 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 虚拟头节点简化边界处理 ListNode dummy(0); ListNode* cur dummy; // 双指针遍历按值拼接 while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } // 拼接剩余节点 cur-next l1 ? l1 : l2; return dummy.next; } };3. 复杂度分析时间复杂度O (n log n)。分割递归深度为 O (log n)每层合并操作遍历 O (n) 个节点总复杂度为 O (n log n)。空间复杂度O (log n)。递归调用栈的深度为链表长度的对数级不满足进阶 O (1) 要求但代码清晰易理解适合入门与面试口述。四、解法二自底向上迭代归并O (1) 空间最优解1. 算法思路为满足进阶 O (1) 空间要求用迭代替代递归核心是 “从小到大逐步合并有序子链表”初始化计算链表长度定义子链表长度subLen 1初始仅单节点有序迭代合并按subLen切分链表为多个有序子链表两两合并每次合并后subLen翻倍1→2→4→...终止条件当subLen 链表长度时所有子链表合并完成得到最终有序链表。2. 完整 C 代码cpp运行class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; // 1. 计算链表长度 int len 0; ListNode* cur head; while (cur) { len; cur cur-next; } // 2. 初始化虚拟头节点统一处理头节点变化 ListNode dummy(0); dummy.next head; ListNode* prev dummy; // 记录已合并部分的尾节点 ListNode* curr dummy.next; // 待处理的链表头 // 3. 自底向上迭代合并 for (int subLen 1; subLen len; subLen * 2) { prev dummy; curr dummy.next; while (curr) { // 切分第一个长度为subLen的子链表 ListNode* l1 curr; ListNode* l2 cut(l1, subLen); // 切分后返回第二个子链表头 // 切分第二个长度为subLen的子链表curr指向剩余链表头 curr cut(l2, subLen); // 合并两个有序子链表拼接至已合并部分尾部 prev-next mergeTwoLists(l1, l2); // 移动prev到合并后链表的尾部 while (prev-next) { prev prev-next; } } } return dummy.next; } private: // 核心工具切分链表返回剩余链表头同时截断前n个节点 ListNode* cut(ListNode* head, int n) { ListNode* p head; // 移动n-1步到达第n个节点 while (--n 0 p) { p p-next; } if (!p) return nullptr; // 不足n个节点返回空 ListNode* nextHead p-next; p-next nullptr; // 截断前n个节点 return nextHead; } // 合并两个有序链表与递归解法通用 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next l1 ? l1 : l2; return dummy.next; } };3. 复杂度分析时间复杂度O (n log n)。外层循环控制子链表长度翻倍O (log n) 次内层循环每次遍历整个链表O (n)总复杂度 O (n log n)。空间复杂度O (1)。仅使用常数个指针变量dummy/prev/curr等无递归栈开销完美满足进阶要求是面试最优解。五、解题避坑与关键细节截断链表必须置空分割子链表时务必将截断位置的next置为nullptr否则会形成循环引用导致递归 / 迭代死循环。快慢指针初始位置找中点时快指针初始指向head-next而非head否则偶数长度链表会分割不均如4→2→1→3会分割为4→2和1→3若快指针初始为head则分割为4和2→1→3。虚拟头节点的必要性合并链表时使用虚拟头节点可避免单独处理空链表、头节点值较小等边界情况统一拼接逻辑。迭代法的 subLen 翻倍子链表长度必须按 2 的幂次递增1→2→4→...否则无法保证所有子链表有序最终合并结果错误。六、总结与拓展LeetCode 148「排序链表」的核心是归并排序在链表上的适配两种解法各有侧重递归归并代码逻辑清晰契合分治思想适合理解算法本质面试中可快速口述思路迭代归并空间复杂度最优是进阶要求的标准解法适合追求极致性能的实战场景。 链表--排序链表
一、题目核心解析1. 题目要求给定单链表的头节点head将链表按升序排列并返回排序后的链表。输入示例head [4,2,1,3]→ 输出[1,2,3,4]数据范围链表节点数∈(0, 5×10⁴)节点值∈[-10⁵, 10⁵]进阶挑战在O (n log n) 时间、O (1) 空间内完成排序2. 算法选型分析链表的非连续存储特性直接排除了数组中高效的随机访问类排序。结合复杂度要求算法选型如下表格排序算法时间复杂度空间复杂度适配性冒泡 / 插入排序O(n²)O(1)❌ 超时无法处理大数据量快速排序平均 O (n log n)O(log n)❌ 链表随机访问开销大递归栈空间不满足进阶要求堆排序O(n log n)O(1)❌ 链表实现复杂无数组下标优势归并排序O(n log n)O(log n)/O(1)✅ 最优解完美适配链表分治与指针操作归并排序的核心优势分治思想天然适配链表分割仅需快慢指针合并仅调整指针无需额外空间是唯一能同时满足时间与空间进阶要求的算法。二、核心前置知识链表操作基石解决这道题前需掌握两个核心基础操作也是解题的 “工具包”1. 快慢指针找中点分割核心通过快慢指针将链表从中间拆分为左右两部分为分治做准备。原理慢指针slow每次走 1 步快指针fast每次走 2 步当fast到达链表尾时slow指向中点。关键细节快指针初始指向head-next确保偶数长度链表时slow指向前半段尾节点便于精准分割。2. 合并两个有序链表合并核心将两个已升序排列的链表合并为一个新的升序链表核心是双指针 虚拟头节点无需创建新节点仅调整指针指向。虚拟头节点dummy简化边界处理无需单独判断空链表统一拼接逻辑。三、解法一自顶向下递归归并清晰易上手1. 算法思路遵循分治 “分割 - 治理 - 合并” 的核心逻辑递归实现分割用快慢指针找到链表中点将链表拆分为左、右两部分治理递归排序左、右两个子链表直到子链表长度为 1天然有序合并将两个有序子链表合并为一个有序链表回溯得到最终结果。2. 完整 C 代码cpp运行/** * 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) { // 递归终止条件空链表或单节点链表天然有序 if (!head || !head-next) { return head; } // 1. 快慢指针找中点分割链表 ListNode* mid findMid(head); ListNode* rightHead mid-next; mid-next nullptr; // 切断左、右子链表避免循环引用 // 2. 递归排序左、右子链表 ListNode* leftSorted sortList(head); ListNode* rightSorted sortList(rightHead); // 3. 合并两个有序链表 return mergeTwoLists(leftSorted, rightSorted); } private: // 快慢指针找链表中点前半段尾节点 ListNode* findMid(ListNode* head) { ListNode* slow head; ListNode* fast head-next; // 关键偶数长度时指向中点前一位 while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; } // 合并两个有序链表核心工具函数 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 虚拟头节点简化边界处理 ListNode dummy(0); ListNode* cur dummy; // 双指针遍历按值拼接 while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } // 拼接剩余节点 cur-next l1 ? l1 : l2; return dummy.next; } };3. 复杂度分析时间复杂度O (n log n)。分割递归深度为 O (log n)每层合并操作遍历 O (n) 个节点总复杂度为 O (n log n)。空间复杂度O (log n)。递归调用栈的深度为链表长度的对数级不满足进阶 O (1) 要求但代码清晰易理解适合入门与面试口述。四、解法二自底向上迭代归并O (1) 空间最优解1. 算法思路为满足进阶 O (1) 空间要求用迭代替代递归核心是 “从小到大逐步合并有序子链表”初始化计算链表长度定义子链表长度subLen 1初始仅单节点有序迭代合并按subLen切分链表为多个有序子链表两两合并每次合并后subLen翻倍1→2→4→...终止条件当subLen 链表长度时所有子链表合并完成得到最终有序链表。2. 完整 C 代码cpp运行class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; // 1. 计算链表长度 int len 0; ListNode* cur head; while (cur) { len; cur cur-next; } // 2. 初始化虚拟头节点统一处理头节点变化 ListNode dummy(0); dummy.next head; ListNode* prev dummy; // 记录已合并部分的尾节点 ListNode* curr dummy.next; // 待处理的链表头 // 3. 自底向上迭代合并 for (int subLen 1; subLen len; subLen * 2) { prev dummy; curr dummy.next; while (curr) { // 切分第一个长度为subLen的子链表 ListNode* l1 curr; ListNode* l2 cut(l1, subLen); // 切分后返回第二个子链表头 // 切分第二个长度为subLen的子链表curr指向剩余链表头 curr cut(l2, subLen); // 合并两个有序子链表拼接至已合并部分尾部 prev-next mergeTwoLists(l1, l2); // 移动prev到合并后链表的尾部 while (prev-next) { prev prev-next; } } } return dummy.next; } private: // 核心工具切分链表返回剩余链表头同时截断前n个节点 ListNode* cut(ListNode* head, int n) { ListNode* p head; // 移动n-1步到达第n个节点 while (--n 0 p) { p p-next; } if (!p) return nullptr; // 不足n个节点返回空 ListNode* nextHead p-next; p-next nullptr; // 截断前n个节点 return nextHead; } // 合并两个有序链表与递归解法通用 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next l1 ? l1 : l2; return dummy.next; } };3. 复杂度分析时间复杂度O (n log n)。外层循环控制子链表长度翻倍O (log n) 次内层循环每次遍历整个链表O (n)总复杂度 O (n log n)。空间复杂度O (1)。仅使用常数个指针变量dummy/prev/curr等无递归栈开销完美满足进阶要求是面试最优解。五、解题避坑与关键细节截断链表必须置空分割子链表时务必将截断位置的next置为nullptr否则会形成循环引用导致递归 / 迭代死循环。快慢指针初始位置找中点时快指针初始指向head-next而非head否则偶数长度链表会分割不均如4→2→1→3会分割为4→2和1→3若快指针初始为head则分割为4和2→1→3。虚拟头节点的必要性合并链表时使用虚拟头节点可避免单独处理空链表、头节点值较小等边界情况统一拼接逻辑。迭代法的 subLen 翻倍子链表长度必须按 2 的幂次递增1→2→4→...否则无法保证所有子链表有序最终合并结果错误。六、总结与拓展LeetCode 148「排序链表」的核心是归并排序在链表上的适配两种解法各有侧重递归归并代码逻辑清晰契合分治思想适合理解算法本质面试中可快速口述思路迭代归并空间复杂度最优是进阶要求的标准解法适合追求极致性能的实战场景。