LeetCode 148.排序链表 超详细技术解析（含O(n log n)最优解）

LeetCode 148.排序链表 超详细技术解析含O(n log n)最优解 全网最清晰易懂解析 | 覆盖3种解法暴力/归并/快排重点突破进阶要求O(n log n)时间常数空间 | 代码可直接复制AC一、题目描述精简核心进阶要求二、解题前置知识必看三、三种解法详解从易到难逐步优化3.1 解法一暴力法简单易实现不满足进阶要求3.2 解法二归并排序递归版满足时间要求不满足空间要求3.3 解法三归并排序迭代版满足进阶要求O(n log n)时间常数空间3.4 补充解法快速排序链表版不稳定慎用四、代码逐行详解新手必看五、示例验证与题目案例完全匹配六、复杂度分析重点对比各解法七、进阶要求突破面试高频考点八、常见避坑指南面试易错点九、总结核心要点提炼一、题目描述精简核心进阶要求给定一个单链表的头节点head将其按升序排列返回复排序后的链表头节点。核心约束链表节点数范围[0, 5×10⁴]数据量较大低效排序会超时节点值范围[-10⁵, 10⁵]包含负数需考虑正负值排序空链表直接返回空示例3场景。进阶要求面试重点请在O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序。示例提示示例1输入 head [4,2,1,3] → 输出 [1,2,3,4]示例2输入 head [-1,5,3,4,0] → 输出 [-1,0,3,4,5]示例3输入 head [] → 输出 []。关键思考链表排序与数组排序的核心区别链表无法随机访问元素因此冒泡、插入等O(n²)排序效率极低快排、归并排序可适配链表但需优化空间复杂度以满足进阶要求。二、解题前置知识必看1. 链表基础结构题目给定不可修改# Definition for singly-linked list.classListNode:def__init__(self,val0,nextNone):self.valval self.nextnext2. 核心排序算法选型适配链表O(n²)排序冒泡、插入不适用于本题节点数5×10⁴时超时严重O(n log n)排序归并、快排适配本题其中归并排序更易实现常数空间迭代版是本题最优解堆排序链表实现复杂空间复杂度难以优化到常数级不推荐。3. 归并排序核心思想重点分治思想将链表拆分为两个子链表分别排序后再将两个有序子链表合并为一个有序链表重复此过程直到整个链表有序。4. 快排核心思想补充选基准节点将链表分为“小于基准”“等于基准”“大于基准”三部分递归排序左右两部分最后拼接三部分。三、三种解法详解从易到难逐步优化重点掌握「归并排序迭代版」完全满足进阶要求是面试高频考点其他解法用于理解思路、对比差异。3.1 解法一暴力法简单易实现不满足进阶要求3.1.1 核心思路遍历链表将所有节点的值存入数组对数组进行排序Python内置sort时间O(n log n)重新构建链表将排序后的数组值依次赋值给新节点拼接成有序链表。核心优势思路简单代码量少易实现核心缺点空间复杂度O(n)不满足进阶要求常数空间。3.1.2 代码实现fromtypingimportOptional# Definition for singly-linked list.classListNode:def__init__(self,val0,nextNone):self.valval self.nextnextclassSolution:defsortList(self,head:Optional[ListNode])-Optional[ListNode]:# 边界处理空链表或单个节点直接返回ifnotheadornothead.next:returnhead# 1. 遍历链表收集所有节点值val_list[]currheadwhilecurr:val_list.append(curr.val)currcurr.next# 2. 对数组排序Python内置sort时间O(n log n)val_list.sort()# 3. 重新构建有序链表dummyListNode(0)# 虚拟头节点方便拼接currdummyforvalinval_list:curr.nextListNode(val)currcurr.next# 返回排序后链表的头节点跳过虚拟头returndummy.next3.2 解法二归并排序递归版满足时间要求不满足空间要求3.2.1 核心思路分治合并拆分分治用「快慢指针」找到链表中点将链表拆分为左、右两个子链表递归分别对左、右子链表进行归并排序直到子链表只有单个节点单个节点即有序合并将两个有序子链表合并为一个有序链表类似LeetCode 21.合并两个有序链表。核心优势时间复杂度O(n log n)思路清晰易理解核心缺点递归栈占用空间O(log n)不满足进阶要求常数空间。3.2.2 代码实现fromtypingimportOptional# Definition for singly-linked list.classListNode:def__init__(self,val0,nextNone):self.valval self.nextnextclassSolution:defsortList(self,head:Optional[ListNode])-Optional[ListNode]:# 递归终止条件空链表或单个节点直接返回已有序ifnotheadornothead.next:returnhead# 第一步找到链表中点拆分链表快慢指针法slow,fasthead,head.next# 快指针比慢指针快一步确保拆分均匀whilefastandfast.next:slowslow.next# 慢指针走一步fastfast.next.next# 快指针走两步right_headslow.next# 右子链表头节点slow.nextNone# 拆分左、右子链表切断连接# 第二步递归排序左、右子链表left_sortedself.sortList(head)# 左子链表排序right_sortedself.sortList(right_head)# 右子链表排序# 第三步合并两个有序子链表returnself.merge(left_sorted,right_sorted)# 辅助函数合并两个有序链表返回合并后的头节点defmerge(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:dummyListNode(0)# 虚拟头节点简化合并逻辑currdummy# 双指针遍历两个链表按值大小拼接whilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.next# 拼接剩余节点其中一个链表已遍历完curr.nextl1ifl1elsel2returndummy.next3.3 解法三归并排序迭代版满足进阶要求3.3.1 核心思路迭代分治合并摒弃递归用迭代方式实现“分治合并”将空间复杂度优化到O(1)完全满足进阶要求初始化计算链表长度定义合并的“步长”初始步长为1每次翻倍迭代合并按当前步长将链表拆分为多个长度为步长的子链表两两合并相邻的子链表得到长度为2×步长的有序子链表步长翻倍重复上述过程直到步长大于链表长度此时整个链表有序。核心优势时间复杂度O(n log n)空间复杂度O(1)满足进阶要求面试首选核心缺点代码逻辑较复杂需注意边界处理。3.3.2 代码实现面试重点fromtypingimportOptional# Definition for singly-linked list.classListNode:def__init__(self,val0,nextNone):self.valval self.nextnextclassSolution:defsortList(self,head:Optional[ListNode])-Optional[ListNode]:# 边界处理空链表或单个节点直接返回ifnotheadornothead.next:returnhead# 第一步计算链表长度用于确定迭代终止条件length0currheadwhilecurr:length1currcurr.next# 第二步初始化虚拟头节点方便后续合并操作dummyListNode(0,head)# 第三步迭代分治合并步长从1开始每次翻倍step1whilesteplength:prevdummy# 每次合并的前驱节点用于拼接合并后的链表currdummy.next# 当前待合并的节点whilecurr:# 1. 找到第一个子链表长度为stepleftcurrfor_inrange(step-1):ifcurr.next:currcurr.nextelse:break# 不足step个节点直接作为左链表rightcurr.next# 第二个子链表的头节点curr.nextNone# 切断左链表与后续节点的连接# 2. 找到第二个子链表长度为stepcurrrightfor_inrange(step-1):ifcurrandcurr.next:currcurr.nextelse:breaknext_nodeNone# 保存下一组待合并的节点头ifcurr:next_nodecurr.nextcurr.nextNone# 切断右链表与后续节点的连接# 3. 合并当前两个有序子链表mergedself.merge(left,right)# 4. 将合并后的链表拼接到底层链表中prev.nextmerged# 5. 更新prev到合并后链表的末尾准备下一组合并whileprev.next:prevprev.next# 6. 移动curr到下一组待合并的节点currnext_node# 步长翻倍分治的层级提升step1# 等价于 step step * 2# 返回排序后的链表头节点returndummy.next# 辅助函数合并两个有序链表与递归版一致defmerge(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:dummyListNode(0)currdummywhilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.nextcurr.nextl1ifl1elsel2returndummy.next3.4 补充解法快速排序链表版不稳定慎用3.4.1 核心思路选基准节点通常选链表头节点或中间节点遍历链表将节点分为三部分小于基准、等于基准、大于基准递归排序“小于基准”和“大于基准”的两部分拼接三部分链表小于→等于→大于返回排序后的头节点。核心说明链表快排时间复杂度平均O(n log n)最坏O(n²)且不稳定空间复杂度O(log n)递归栈不满足进阶要求面试中不如归并排序实用仅作补充。3.4.2 代码实现fromtypingimportOptional# Definition for singly-linked list.classListNode:def__init__(self,val0,nextNone):self.valval self.nextnextclassSolution:defsortList(self,head:Optional[ListNode])-Optional[ListNode]:# 递归终止条件空链表或单个节点ifnotheadornothead.next:returnhead# 选基准节点此处选头节点可优化为随机选避免最坏情况pivothead# 定义三个虚拟头节点分别对应小于、等于、大于基准的节点less_dummyListNode(0)equal_dummyListNode(0)greater_dummyListNode(0)# 定义三个指针用于拼接对应链表lessless_dummy equalequal_dummy greatergreater_dummy currheadwhilecurr:ifcurr.valpivot.val:less.nextcurr lessless.nextelifcurr.valpivot.val:equal.nextcurr equalequal.nextelse:greater.nextcurr greatergreater.nextcurrcurr.next# 切断链表避免循环引用less.nextNoneequal.nextNonegreater.nextNone# 递归排序小于和大于基准的链表less_sortedself.sortList(less_dummy.next)greater_sortedself.sortList(greater_dummy.next)# 拼接三部分小于 → 等于 → 大于# 先找到less_sorted的末尾节点ifless_sorted:curr_lessless_sortedwhilecurr_less.next:curr_lesscurr_less.nextcurr_less.nextequal_dummy.nextelse:less_sortedequal_dummy.next# 找到equal部分的末尾节点拼接greater_sortedcurr_equalless_sortedwhilecurr_equal.next:curr_equalcurr_equal.nextcurr_equal.nextgreater_sortedreturnless_sorted四、代码逐行详解新手必看重点讲迭代版归并重点解析「归并排序迭代版」这是面试高频考点也是满足进阶要求的最优解。4.1 边界处理ifnotheadornothead.next:returnhead空链表或只有单个节点的链表本身就是有序的直接返回避免多余计算。4.2 计算链表长度length0currheadwhilecurr:length1currcurr.next用于确定迭代的终止条件当步长step大于链表长度时整个链表已完成排序。4.3 初始化虚拟头节点dummyListNode(0,head)虚拟头节点的next指向原链表头方便后续合并操作无需单独处理头节点拼接。4.4 迭代分治合并核心部分step1whilesteplength:prevdummy currdummy.nextwhilecurr:# 1. 拆分左子链表leftcurrfor_inrange(step-1):ifcurr.next:currcurr.nextelse:breakrightcurr.nextcurr.nextNone# 2. 拆分右子链表currrightfor_inrange(step-1):ifcurrandcurr.next:currcurr.nextelse:breaknext_nodeNoneifcurr:next_nodecurr.nextcurr.nextNone# 3. 合并左、右子链表mergedself.merge(left,right)# 4. 拼接合并后的链表prev.nextmerged# 5. 更新prev到合并链表末尾whileprev.next:prevprev.next# 6. 处理下一组currnext_node# 步长翻倍step1step初始化1初始时将链表拆分为单个节点长度1本身有序两两合并prev指针用于拼接合并后的子链表每次合并后prev移动到合并链表的末尾为下一次合并做准备拆分左、右子链表按当前step长度拆分出两个相邻的子链表并用curr.next None切断连接避免合并时混乱next_node保存下一组待合并的节点头避免拆分时丢失后续链表step 1步长翻倍每次迭代后子链表长度翻倍直到step大于链表长度排序完成。4.5 合并两个有序链表辅助函数defmerge(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:dummyListNode(0)currdummywhilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.nextcurr.nextl1ifl1elsel2returndummy.next经典的“合并两个有序链表”逻辑用虚拟头节点简化拼接双指针遍历按值大小依次拼接最后拼接剩余节点。五、示例验证与题目案例完全匹配示例1 验证输入head [4,2,1,3]迭代版归并过程初始step1链表4→2→1→3拆分后为 [4], [2], [1], [3]合并[4]和[2] → [2→4]合并[1]和[3] → [1→3]此时链表2→4→1→3step翻倍为2拆分后为 [2→4], [1→3]合并两个子链表 → [1→2→3→4]step翻倍为4大于链表长度4排序完成返回[1→2→3→4] ✅。示例2 验证输入head [-1,5,3,4,0]step迭代过程1→2→4→885最终合并后得到 [-1→0→3→4→5]与输出一致 ✅。示例3 验证输入head []边界处理直接返回空链表 ✅。六、复杂度分析重点对比各解法解法时间复杂度空间复杂度是否满足进阶要求优势缺点暴力法O(n log n)数组排序O(n)存储节点值否思路简单代码量少空间开销大不满足进阶要求归并排序递归版O(n log n)O(log n)递归栈否思路清晰易理解稳定排序递归栈占用空间不满足进阶要求归并排序迭代版O(n log n)O(1)仅用常数变量是满足进阶要求稳定排序面试首选代码逻辑较复杂边界处理多快速排序链表版平均O(n log n)最坏O(n²)O(log n)递归栈否平均效率高不稳定最坏情况效率低不满足进阶要求七、进阶要求突破面试高频考点进阶要求O(n log n)时间复杂度 常数级空间复杂度核心突破点时间复杂度突破必须选择O(n log n)排序算法归并、快排排除O(n²)算法空间复杂度突破摒弃递归递归栈占用O(log n)空间用迭代方式实现归并排序仅使用常数个指针变量空间复杂度优化到O(1)。面试重点提问如何优化归并排序的空间复杂度答用迭代分治替代递归分治通过步长迭代拆分链表两两合并全程仅使用虚拟头节点、prev、curr等常数个指针不使用额外数组或栈实现常数空间。八、常见避坑指南面试易错点坑1递归版归并忘记切断链表错误原因拆分左、右子链表时未将slow.next设为None导致合并时链表混乱正确做法拆分后slow.next None切断左、右子链表的连接。坑2迭代版归并步长计算错误错误原因step初始值设为0或翻倍方式错误如step step 1正确做法step初始为1每次翻倍step 1直到step 链表长度。坑3合并链表时忘记拼接剩余节点错误原因双指针遍历结束后未将剩余的l1或l2节点拼接正确做法curr.next l1 if l1 else l2拼接剩余节点。坑4快排选基准不当导致最坏情况错误原因固定选头节点作为基准当链表已有序时时间复杂度变为O(n²)优化方案随机选择基准节点避免最坏情况。坑5忽略空链表或单个节点的边界场景错误原因未做边界处理导致空指针异常正确做法开头判断if not head or not head.next直接返回head。九、总结核心要点提炼148.排序链表的核心是「选择合适的排序算法优化空间复杂度」面试重点掌握以下3点解法选型优先选择「归并排序迭代版」完全满足进阶要求是面试最优解核心逻辑分治思想拆分→排序→合并迭代版通过步长控制拆分和合并实现常数空间避坑重点切断链表、拼接剩余节点、边界处理、步长翻倍正确。本题考察的核心是「链表操作」和「排序算法的优化」掌握迭代版归并排序后可快速迁移到类似的链表排序问题面试中遇到可直接拿下