LeetCode 148. 排序链表：归并排序详解

拆解 LeetCode 中等难度题目「148. 排序链表」这道题核心考察链表的归并排序是链表操作与排序算法结合的经典题型也是面试中高频出现的考点。本文会从题目分析、解题思路、代码拆解到注意事项一步步帮大家搞懂这道题新手也能轻松跟上。一、题目回顾题目要求给你链表的头结点 head 请将其按升序排列并返回排序后的链表。补充说明链表中节点的数目范围是 [0, 5 * 10⁴]-10⁵ ≤ Node.val ≤ 10⁵进阶要求你可以在 O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序吗本文解法将满足这一要求二、解题思路为什么选择归并排序首先思考链表排序和数组排序有什么区别数组可以用快速排序随机访问效率高但链表的随机访问效率低O(n)而归并排序的核心是「分治合并」刚好适配链表的特性——分治时无需随机访问合并时只需调整指针且时间复杂度天然是 O(n log n)完美契合题目要求。归并排序的整体思路链表适配版分将链表从中间分成左右两个子链表递归拆分直到每个子链表只包含一个节点单个节点本身就是有序的治将两个有序的子链表合并成一个有序的链表合递归合并所有子链表最终得到完整的有序链表。关键难点如何找到链表的中间节点分治的核心、如何高效合并两个有序链表。三、完整代码TypeScript 版先贴出完整可运行代码后续逐部分拆解大家可以先整体感知classListNode{val:numbernext:ListNode|nullconstructor(val?:number,next?:ListNode|null){this.val(valundefined?0:val)this.next(nextundefined?null:next)}}functionsortList(head:ListNode|null):ListNode|null{// 边界处理空链表直接返回if(headnull){returnnull;}// 1. 找到链表中间节点二分核心constfindMid(left:ListNode,right:ListNode|null):ListNode{if(leftright){returnleft;}// 快慢指针慢指针走1步快指针走2步快指针到尾时慢指针在中间letslow:ListNode|null|undefinedleft;letfast:ListNode|null|undefinedleft.next;// 快指针不越界right是区间边界不包含while(fast!nullfast?.next!null){slowslow.next!;fastfast.next?.next;}returnslow;};// 2. 递归分治合并constdfs(left:ListNode|null,right:ListNode|null):ListNode|null{if(leftnull){returnnull;}// 单个节点直接返回递归终止条件if(leftright){returnleft;}// 找中间节点拆分链表constmidfindMid(left,right);constrightHeadmid.next;// 右子链表的头节点mid.nextnull;// 切断左右子链表避免循环// 递归拆分左、右子链表lettemp_1dfs(left,mid);lettemp_2dfs(rightHead,right);// 合并两个有序子链表returnmergeTwoLists(temp_1,temp_2);};// 3. 合并两个有序链表辅助函数constmergeTwoLists(l1:ListNode|null,l2:ListNode|null):ListNode|null{constdummyHeadnewListNode(0);// 虚拟头节点简化合并逻辑lettempdummyHead;// 双指针遍历两个链表按值大小拼接while(l1!nulll2!null){if(l1.vall2.val){temp.nextl1;l1l1.next;}else{temp.nextl2;l2l2.next;}temptemp.next;// 移动指针}// 拼接剩余节点其中一个链表可能已遍历完temp.nextl1!null?l1:l2;returndummyHead.next;// 返回合并后的链表头};// 调用递归函数初始区间头节点到null右边界不包含returndfs(head,null);};四、代码逐部分拆解1. 链表节点类ListNode题目已给出节点类的定义核心是两个属性val节点存储的值number类型next指向后续节点的指针可能为null代表链表尾。构造函数做了默认值处理val默认0next默认null避免传入undefined时报错。2. 边界处理if(headnull){returnnull;}当输入链表为空时直接返回null避免后续递归出现异常这是所有链表题的常规操作。3. 找到链表中间节点findMid函数这是分治的核心采用「快慢指针法」效率比遍历计数找中间节点更高O(n/2) 时间。核心逻辑慢指针slow初始指向left每次走1步快指针fast初始指向left.next每次走2步当快指针无法再走2步fast null 或 fast.next null时慢指针刚好指向链表的中间节点。注意函数参数中的right是「区间边界不包含」比如初始调用时right为null代表拆分到链表末尾。4. 递归分治dfs函数dfs函数的作用是「拆分链表合并链表」递归终止条件是当left right时说明当前子链表只有一个节点直接返回单个节点有序。关键步骤调用findMid找到中间节点mid将mid.next赋值给rightHead右子链表的头并将mid.next设为null切断左右子链表避免递归时循环遍历递归调用dfs分别处理左子链表left到mid和右子链表rightHead到right调用mergeTwoLists将两个有序的子链表合并返回合并后的链表头。5. 合并两个有序链表mergeTwoLists函数这是归并排序的「治」环节也是链表操作的经典场景采用「虚拟头节点双指针」实现。核心逻辑创建虚拟头节点dummyHead值为0无实际意义用于简化链表拼接逻辑无需单独处理头节点temp指针指向dummyHead用于遍历拼接新链表双指针l1、l2分别遍历两个有序子链表每次将值较小的节点拼接到temp.next然后移动对应指针当其中一个链表遍历完后将另一个链表的剩余节点直接拼接到temp.next剩余节点已有序返回dummyHead.next即合并后的有序链表头。6. 主函数调用returndfs(head,null);初始调用dfs时左边界为head链表头右边界为null不包含即链表尾开启递归分治与合并。五、关键注意事项避坑点拆分链表时必须将mid.next设为null否则左右子链表会相连递归时会陷入死循环快慢指针的初始位置fast要比slow超前一步left.next否则当链表长度为2时会无法拆分比如1→2slow和fast都指向1无法分成[1]和[2]合并链表时虚拟头节点的使用是关键能避免单独判断头节点的麻烦提升代码简洁度递归终止条件left right单个节点否则会无限递归导致栈溢出。六、复杂度分析满足进阶要求时间复杂度O(n log n)归并排序的标准时间复杂度分治环节是O(log n)层每一层的合并环节是O(n)整体为O(n log n)空间复杂度O(log n)递归调用栈的深度为O(log n)分治的层数没有使用额外的数组或哈希表满足常数级空间的进阶要求若不考虑递归栈空间复杂度为O(1)。七、总结LeetCode 148.排序链表的核心是「链表的归并排序」核心难点在于「找中间节点」和「合并有序链表」而快慢指针和虚拟头节点是解决这两个难点的关键技巧。这道题的价值在于它不仅考察了链表的基本操作还融合了归并排序的分治思想是面试中考察「链表排序」的典型代表。建议大家多动手调试代码重点理解拆分链表时的指针切断、合并链表时的双指针移动掌握后能轻松应对同类链表排序问题。