hot100 排序链表(148)

本题采用自顶向下的归并排序算法又称“二分滑窗切分与归并重组法”解决单链表的升序排列问题。其核心本质是利用分治策略通过快慢指针在同向拓扑结构中步进以锁定链表中点执行物理截断将其逐级裂变为单节点子问题再通过双指针有序归并实现链路的重新编排。当前提供的源码实现了在时间复杂度 O(N log N) 和系统递归栈空间复杂度 O(log N) 条件下的对数阶局部最优检索最终走向是完全重写各节点指针的指向并返回全局升序的头节点。一、 问题本质与数据模型对于由ListNode构成的无序单链表由于其物理内存分布的不连续性与单向指针域next的不可逆性无法像数组结构一样在 O(1) 时间内进行随机物理寻址。因此诸如堆排序、快速排序等依赖高频随机交换位置的算法在链表结构上会引入极高的指针维护开销。归并排序Merge Sort天然适合链表这一拓扑结构。在重组阶段链表的归并操作仅需要改变现有节点的指针指向即可在 O(1) 的额外堆内存损耗下完成有序拼接。算法引入了以下核心数据控制流模型“快慢指针双倍步进截断模型”设置fast、slow和pre三个指针通过快指针移动速度为慢指针两倍的物理规律当快指针触底时慢指针精准卡位在后半段的起始点。通过将前驱节点pre.next置为null实现原链表的完全物理解耦。“分治递归收敛模型”将长链表持续一分为二直至分裂出的子链表仅包含单个节点或为空此时局部自然满足升序条件构成分治的基准退出边界Base Case。二、 算法演进对比在解决链表全排序问题时自顶向下归并法在指针开销与时间收敛上表现出确定的线性对数级特征解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷外部数组中转排序法O(N log N)O(N)将链表节点值全部复制到数组中利用快速排序后重新物理构建一条新链表产生了与链表规模呈正比的外部存储空间消耗破坏了原地修改的原则自顶向下归并法当前解法O(N log N)O(log N)通过快慢指针执行中点物理分割深度递归后进行原地双指针归并缝合系统的递归调用栈深度与链表长度的对数呈正比无法实现绝对意义上的 O(1) 额外空间自底向上迭代归并法O(N log N)O(1)利用循环引入固定的步长1, 2, 4...在链表内部逐段执行局部归并与桥接控制变量极其繁琐需要引入大量复杂的指针域边界缝合逻辑代码可读性低三、 核心分支控制逻辑与决策证明当前源码的控制流由一个递归主函数sortList、一个切分函数mid以及一个二路归并函数merge组合而成其内部决策及物理证明如下1. 递归终止条件边界if (head null || head.next null)执行直接返回当前head。数学证明当节点数为 0 或 1 时链表在拓扑逻辑上不具备产生逆序的可能性。结论当前子区间已收敛为最小物理单元无需进一步切分直接向上层触发归并流程。2. 快慢指针中点切分mid(ListNode head)执行fast fast.next.next; slow slow.next;并在循环后执行pre.next null;。数学证明设链表总节点数为 N。由于fast每次步进 2 个节点slow每次步进 1 个节点当fast遍历完 N 个节点触底时slow精准移动了 N/2 步即停留于中间节点。结论pre作为slow的前驱执行pre.next null彻底斩断了前半段与后半段的物理关联将输入链表均分为两条独立的子链表其头节点分别为head与slow。3. 双指针原地有序归并merge(ListNode p, ListNode q)执行利用dummy节点作为控制哨兵通过while (p ! null q ! null)执行线性扫描较小者挂载到cur.next。结论该结构保证了两个已排序的子链表能够以 $O(1)$ 的额外堆内存损耗重组为一条满足全局升序的新链表。四、 算法执行状态机步进示例以输入无序链表head [4, 2, 1, 3]为例自顶向下切分及自底向上归并的整体状态演进过程如下表所示步骤阶段作用的局部拓扑数据执行的控制动作产生的中间断开状态 / 归并状态拓扑物理剩余状态说明初始调用[4, 2, 1, 3]启动主函数sortList进入第一层分治链表未发生拆解第一级切分[4, 2, 1, 3]调用mid函数锁定中点断裂为两段head1[4, 2],head2[1, 3]成功切分为左右两个子链表区域第二级左切分head1[4, 2]对左段递归调用mid断裂为两段[4]和[2]满足终止条件退化为基础单元第一级左归并[4]与[2]对左侧两个单节点执行merge归并重组为升序链表[2, 4]左侧子区间局部升序完成第二级右切分head2[1, 3]对右段递归调用mid断裂为两段[1]和[3]满足终止条件退化为基础单元第一级右归并[1]与[3]对右侧两个单节点执行merge归并重组为升序链表[1, 3]右侧子区间局部升序完成最终全局归并[2, 4]与[1, 3]触发最外层merge(head1, head2)通过双指针重定向输出[1, 2, 3, 4]全链表有序化指针重组完毕五、 源码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode sortList(ListNode head) { // 基准出口边界若链表为空或仅剩单一节点无需排序直接终止递归 if (head null || head.next null) { return head; } // 步骤 1寻找当前链表的中点并将链表从中间物理断开返回后半段的头节点 ListNode head2 mid(head); // 步骤 2对前半段链表执行递归归并排序 ListNode head1 sortList(head); // 对后半段链表执行递归归并排序 head2 sortList(head2); // 步骤 3将两段已经实现局部升序的链表融合成一个全局有序的链表 return merge(head1, head2); } private ListNode mid(ListNode head) { // 初始化快、慢指针以及用于记录慢指针前驱的 pre 指针 ListNode fast head; ListNode slow head; ListNode pre head; // 快慢指针双倍速推进控制网 while (fast ! null fast.next ! null) { pre slow; // 记录 slow 指针移动前的前驱位置 fast fast.next.next; // 快指针单次步进 2 个节点 slow slow.next; // 慢指针单次步进 1 个节点 } // 核心切分动作斩断前半段尾部与后半段头部的指针链接 pre.next null; // 返回后半段链表的头节点 return slow; } private ListNode merge(ListNode p, ListNode q) { // 创建虚拟哑节点 dummy用作合并过程中的固定边界哨兵 ListNode dummy new ListNode(); // 初始化工作控制指针 cur 指向哑节点 ListNode cur dummy; // 双指针线性扫描比对 while (p ! null q ! null) { if (p.val q.val) { cur.next p; p p.next; } else { cur.next q; q q.next; } // 新链表控制指针同步后移 cur cur.next; } // 边界残留处理将尚未消耗完毕的非空剩余链表段直接整段挂载 cur.next (p ! null) ? p : q; // 返回剥离哨兵后的真实有序链表头节点 return dummy.next; } }六、 复杂度分析1. 时间复杂度O(N log N)分析切分阶段每一层递归都需要调用一次mid函数其耗时与当前子链表的长度呈线性关系。对于长度为 N 的链表二分切分的总层数为 log N。归并阶段同层所有子链表执行merge操作时的基本比较次数之和恒等于 N。结论整个归并排序模型的计算工作量可以表达为每一层线性扫描耗时与对数阶层数的乘积整体时间损耗恒定为 O(N log N)。2. 空间复杂度O(log N)分析从堆内存Heap的角度来看算法完全是在原节点上修改指针域指向没有开辟任何与输入规模成正比的全新临时节点。然而由于该解法采用了自顶向下的递归架构在程序执行期间操作系统需要开辟隐式的系统递归调用栈来保存当前的局部变量状态。结论二分递归树的最大深度为 log N因此系统栈空间的物理消耗恒定为对数阶 O(log N)。