当前位置：首页 > news >正文

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

news 2026/5/12 19:00:23

拆解 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=(val===undefined?0:val)this.next=(next===undefined?null:next)}}functionsortList(head:ListNode|null):ListNode|null{// 边界处理：空链表直接返回if(head===null){returnnull;}// 1. 找到链表中间节点（二分核心）constfindMid=(left:ListNode,right:ListNode|null):ListNode=>{if(left===right){returnleft;}// 快慢指针：慢指针走1步，快指针走2步，快指针到尾时，慢指针在中间letslow:ListNode|null|undefined=left;letfast:ListNode|null|undefined=left.next;// 快指针不越界（right是区间边界，不包含）while(fast!==null&&fast?.next!==null){slow=slow.next!;fast=fast.next?.next;}returnslow;};// 2. 递归分治+合并constdfs=(left:ListNode|null,right:ListNode|null):ListNode|null=>{if(left===null){returnnull;}// 单个节点，直接返回（递归终止条件）if(left===right){returnleft;}// 找中间节点，拆分链表constmid=findMid(left,right);constrightHead=mid.next;// 右子链表的头节点mid.next=null;// 切断左右子链表，避免循环// 递归拆分左、右子链表lettemp_1=dfs(left,mid);lettemp_2=dfs(rightHead,right);// 合并两个有序子链表returnmergeTwoLists(temp_1,temp_2);};// 3. 合并两个有序链表（辅助函数）constmergeTwoLists=(l1:ListNode|null,l2:ListNode|null):ListNode|null=>{constdummyHead=newListNode(0);// 虚拟头节点，简化合并逻辑lettemp=dummyHead;// 双指针遍历两个链表，按值大小拼接while(l1!==null&&l2!==null){if(l1.val<=l2.val){temp.next=l1;l1=l1.next;}else{temp.next=l2;l2=l2.next;}temp=temp.next;// 移动指针}// 拼接剩余节点（其中一个链表可能已遍历完）temp.next=l1!==null?l1:l2;returndummyHead.next;// 返回合并后的链表头};// 调用递归函数，初始区间：头节点到null（右边界不包含）returndfs(head,null);};

四、代码逐部分拆解

1. 链表节点类（ListNode）

题目已给出节点类的定义，核心是两个属性：

val：节点存储的值（number类型）；
next：指向后续节点的指针（可能为null，代表链表尾）。

构造函数做了默认值处理：val默认0，next默认null，避免传入undefined时报错。

2. 边界处理

if(head===null){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→2，slow和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)）。