排序链表LeetCode 148：归并排序分治+快慢指针，递归与迭代详解

排序链表这题LeetCode第148题可以说是我在热门100题里刷得最揪心的一道。解法逻辑并不绕就是归并排序那一套分治思想但真到自己上手写的时候断链、死循环、空指针各种小毛病轮着来我第一次写完整花了四十多分钟最后还带着一个隐蔽bug。后来反复练了几遍才把递归和迭代两种版本都吃透。这篇文章就是把我从卡壳到写顺的全过程整理出来思路怎么定的、代码怎么拆的、都有哪些坑一次性讲透。你不用怕链表基础差我尽量用最直白的话把每个细节说清。1. 题目拆解排序链表到底在考你什么1.1 两个被反复强调的硬性要求题目本身一句话就能说完给你一个链表的头节点 head把它按升序排序然后返回排序后的链表。但真正决定考察难度的是后面这两条限制时间复杂度要求 O(n log n)额外空间复杂度要求 O(1)如果你不常刷链表题可能觉得这要求不算苛刻。但我们只要往深想一步就会发现这道题几乎把“数组时代”的排序捷径全堵死了。你可以先回想一下对数组排序手写快排、调用库函数怎么着都行。可一旦把数组换成链表事情就不一样了链表节点只能通过 next 指针单向访问没有下标没有随机访问能力这意味着很多在数组上非常順手的操作在链表上根本做不了。所以这道题表面考的是“排序”实际考的是三件事你对分治思想的理解深度你对链表指针操作的熟练程度以及你在复杂约束条件下选择算法的判断力。LeetCode上这道题的讨论区非常热闹原因也在于此——它是一道能拉开差距的题目很多人一看就会一写就废。1.2 为什么常见的排序算法在这里集体失灵先帮大家把几个“看起来可行实际行不通”的路线过一遍。这不仅仅是做题更是以后面试里别人追问你“为什么不用XX排序”时的弹药。插入排序时间复杂度最坏 O(n^2)。虽然链表实现插入排序很简单不需要搬移元素只要找到插入位置改指针就行但题目明确要求 O(n log n)所以直接出局。顺带一提LeetCode第147题“对链表进行插入排序”就是专门让你练这个的可以作为反面教材做一遍。快速排序很多人第一反应是快排。问题是快排的灵魂在于 partition 操作它需要两个指针从两端往中间逼近依赖的是数组的随机访问能力。链表是单向的你只能从头往后遍历虽然可以硬写一个链表版的 partition但每次都要从头扫描指针管理极其繁琐而且最坏情况时间复杂度依然会退化到 O(n^2)。这种解法在面试里属于“能说出口但不推荐”。堆排序堆排序的时间复杂度稳定在 O(n log n)空间复杂度也能做到 O(1)看起来完美。可问题是堆这种数据结构天然是用数组实现的你需要在 O(1) 时间内访问堆顶和交换元素。链表无法做到这些除非你先把链表转成数组那额外空间就是 O(n) 了不符合要求。取巧方案还有一种看着很“聪明”的做法遍历链表把所有 val 收集到一个数组里用 Arrays.sort 或者快速排序排完序再从头遍历链表把值写回去。时间复杂度是 O(n log n)代码也短但它额外用了 O(n) 的空间。LeetCode 官方明确要求 O(1) 空间所以在严格意义上不算过关。网上有些题解会提这种方法面试时你当成思路聊一句可以千万别当主方案讲。把这些方案排除完之后你会发现剩下的最优解基本就只有一个方向归并排序。归并排序的分治思想和链表的结构简直是天作之合。一个链表的拆分只需要找中点然后断开 next 指针就行了两个链表的合并只需要不断比较头节点、把较小的节点串起来就行了整个过程不需要随机访问不需要来回移动指针每一步都是顺手的事。2. 思路定型归并排序天然契合链表结构2.1 先回忆一下归并排序到底是怎么运作的归并排序是最典型的分治算法一次完整的排序分三步走把当前序列从中间分成左右两个子序列递归地对左右两个子序列分别排序把两个已排序的子序列合并成一个完整的有序序列从宏观上看它就是把“排序”这个复杂任务拆成了“切一半各自排好再合并”这三个简单操作。重复这个步骤直到每个子序列只剩一个元素此时子序列天然有序然后逐层合并回去整个序列就有序了。对数组做归并排序时你还需要一个临时数组来存放合并结果所以经典的数组版归并排序空间复杂度是 O(n)。这是它的短板。但链表不一样链表的合并只需要改 next 指针不需要额外的数据存储空间所以链表的归并排序可以把额外空间压得非常低。这个特性让归并排序从“可用”变成了“首选”。2.2 两种实现路线自顶向下和自底向上同样是归并排序落到链表上有两种实现思路面试时这两个版本最好都掌握。自顶向下递归版先找链表的中点把链表切成前后两半递归排序左右两半最后把两个有序链表合并起来。这个版本写起来更符合人的直觉代码结构清晰也是绝大多数题解最先给出的方案。唯一的代价是递归需要栈空间递归深度是 O(log n)所以严格来说额外空间是 O(log n)不是 O(1)。自底向上迭代版不递归而是从长度为1的子链表开始两两合并得到长度为2的有序子链表再两两合并得到长度为4的有序子链表如此反复直到整个链表有序。整个过程只需要几个指针变量额外空间是 O(1)完美契合题目 Follow up 里的 constant space 要求。你可能会问既然递归版更简单我掌握递归版不就行了这里要想清楚两件事。第一LeetCode 这道题的 Follow up 明确问了能不能用 O(1) 空间完成排序如果你只写递归版被追问到空间复杂度时容易卡壳。第二不少大厂面试官会专门让你把递归改成迭代考察你能不能跳出递归的舒适区用循环控制状态。所以我的建议是先写递归版把思路理通再花时间把迭代版啃下来。3. 手把手实现自顶向下归并排序的完整代码3.1 核心步骤一快慢指针精准找中点自顶向下归并排序的第一步是把链表从中间切开。链表不像数组你没法直接算下标取中位数只能借助快慢指针。快慢指针的思路很朴素慢指针 slow 每次走一步快指针 fast 每次走两步。当快指针到达链表末尾时慢指针刚好停在链表的中间。但这里有一个细节非常关键也是很多人在这个步骤上翻车的根源——快慢指针的初始位置。我这里直接给出我的写法配合链表长度各异的场景来理解private ListNode getMid(ListNode head) { ListNode slow head, fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }注意 fast 初始化的是 head.next 而不是 head。这样做的目的是让 slow 在链表长度为偶数时落在中间偏左的位置也就是左半部分的最后一个节点。举个例子链表是 1 - 2 - 3 - 4如果 fast 也初始化为 headslow 最后会停在节点3你把它当成中点断开左半部分就变成了 1-2-3右半部分只剩 4切分不均匀倒还好关键是递归时容易出现左右两边长度分配混乱或者死循环。而 fast 初始化为 head.nextslow 会停在节点2左半部分是 1-2右半部分是 3-4干净利落。拿到中点之后还有一件事必须立刻做把前半段的尾巴断开。也就是 mid.next null。这一步不能省省了你后面 sortList 递归的时候左右两个子链表还藕断丝连合并的时候链表里容易出现环提交上去就是死循环超时。3.2 核心步骤二递归拆分与有序合并找完中点并断链之后整个链表被分成了前后两个独立子链表。把这两个子链表分别扔给 sortList 递归处理等它们各自返回有序链表后再进行合并。合并操作就是我们熟悉的 merge 两个有序链表用 dummy 节点简化头部的空指针判断private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy new ListNode(-1); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } cur.next (l1 ! null) ? l1 : l2; return dummy.next; }merge 的逻辑不复杂核心就是两个指针分别指向两个链表的头节点谁小就先接谁接完之后指针往后移一位。这里有一个容易被忽略的点比较的时候用的是小于等于也就是 l1.val l2.val 时优先接 l1 的节点这个细节保证了排序的稳定性。如果一边已经为空了直接把另一边的剩余链表整体接上就行因为剩余部分已经是有序的。主函数 sortList 就三段式递归终止、中点断开、左右合并public ListNode sortList(ListNode head) { if (head null || head.next null) { return head; } ListNode mid getMid(head); ListNode rightHead mid.next; mid.next null; ListNode left sortList(head); ListNode right sortList(rightHead); return merge(left, right); }整体逻辑非常清爽链表只剩一个节点或者为空直接返回否则找到中点并断开递归处理左右两半最后合并返回。这一段代码的线条很干净建议你手写至少三遍第一遍对着看第二遍不看写第三遍看能不能顺手写出边界条件。这里提一下时间复杂度每层递归都需要完整遍历一次链表的所有节点递归树的高度是 O(log n)所以总时间复杂度是 O(n log n)。空间方面递归调用会占用栈空间深度是 O(log n)这就是前文提到的它不是严格的 O(1) 空间。4. 进阶实现自底向上归并排序真正的O(1)空间4.1 为什么说迭代版才是这道题的完全体递归版写起来舒服但面试官一句“你能把额外空间降到 O(1) 吗”立马就会把人问住。因为递归调用本身的栈空间不是常数级无论你怎么优化语句深度始终是 O(log n)。如果你面对的是严格要求 constant space 的场景就必须请出自底向上的迭代版归并排序。自底向上的核心思想是把“递归切分”这一步完全去掉改成从最小单元开始合并。具体做法是先把链表看成一个个长度为 1 的“天然有序子链表”第一轮两两合并得到若干个长度为 2 的有序子链表第二轮再两两合并得到长度为 4 的有序子链表每轮把子链表长度翻倍直到合并后的长度超过链表总长度整个链表就自然有序了。整个过程只用到有限的几个指针变量额外空间 O(1)时间依然是 O(n log n)。这个思路的难点在于递归版里子链表之间的边界全靠递归天然分割而迭代版里你必须自己手动控制“切到哪里为止”,也就是需要一种操作能把一个长链表按指定长度切下一段来。4.2 cut函数按指定长度切分链表的利器我们定义一个剪断函数 cut(head, n)表示从 head 节点开始切下前 n 个节点然后返回剩余链表的头节点。切下来的这段末尾的 next 会被置为 null和后面的部分彻底断开。private ListNode cut(ListNode head, int n) { ListNode p head; while (--n 0 p ! null) { p p.next; } if (p null) { return null; } ListNode next p.next; p.next null; return next; }这个函数看起来短理解起来需要一点耐心。它做的事情是先让指针 p 沿着链表走 n-1 步也就是从 head 走到第 n 个节点然后记录 p.next 为 next再把 p.next 置为 null相当于把第 n 个节点之后的链条剪断最后返回 nextnext 就是剩余链表的头。如果链表长度不足 n说明没有剩余节点了那 p 会走到 null函数返回 null。举个例子链表是 A - B - C - D调用 cut(head, 2)p 先走到 B然后把 B.next 置为 null返回 C。此时 A - B 是一段独立链表C - D 是剩余链表。这个动作就是迭代版归并排序里最核心的基本操作。4.3 完整代码与逐段拆解有了 cut 函数再配合之前写好的 merge 函数自底向上版本的主逻辑就能拼起来了public ListNode sortList(ListNode head) { if (head null || head.next null) { return head; } int length 0; ListNode node head; while (node ! null) { length; node node.next; } ListNode dummy new ListNode(-1); dummy.next head; for (int subLength 1; subLength length; subLength 1) { ListNode prev dummy; ListNode cur dummy.next; while (cur ! null) { ListNode head1 cur; ListNode head2 cut(head1, subLength); cur cut(head2, subLength); prev.next merge(head1, head2); while (prev.next ! null) { prev prev.next; } } } return dummy.next; }我来逐段拆解这段代码。第一段先计算链表总长度这个是为了让外层循环知道最多要合并到多大的子链表为止。dummy 节点指向原始头节点它会在每一轮合并中帮我们记录合并后的新的链表头。外层 for 循环是最重要的一层subLength 从 1 开始每轮翻倍。每一轮我们都要把整个链表从头到尾遍历一遍把链表分割成多个长度为 subLength 的子链表让相邻的两两合并。循环结束条件 subLength length意思是当子链表长度已经不小于总长度说明整个链表已经是一整段有序链表了不需要再合并下去。内层 while 循环负责真正的一轮合并。prev 指向合并结果的尾部cur 指向当前待处理段的起点。循环体里连续两次调用 cut第一次把 cur 所在的链表切下 subLength 个节点作为 head1第二次把剩余部分再切下 subLength 个节点作为 head2。如果链表已经被切空cur 会变成 null内层循环自然退出。接下来把 head1 和 head2 合并接到 prev.next 上。这里非常关键的一个细节是prev 必须时刻指向“已经合并完成的链表的末尾”。所以每次合并完要写一个 while 循环让 prev 一直往后移动直到走到 null 前一个节点也就是刚刚合并完的那段链表的末尾这样下一次合并结果才能正确拼接上去。这里可能有人会问那如果 head2 在 cut 的时候返回了 null也就是说剩余链表不够一段 subLength 了merge(head1, null) 会返回什么答案是直接返回 head1相当于这段没有和谁合并原样保留。这没有问题因为当剩余子链表长度不足 subLength 时它本身已经是有序的不需要再和空链表合并。后面如果还有更长的合并轮次它自然会作为完整的一段参与下一轮。迭代版的思想比递归版难理解一些我建议你拿一个短一点的链表比如 4 - 2 - 5 - 1 - 3在纸上模拟一遍这个流程感受一下 subLength 从 1 变 2 变 4 时链表的形态如何一步步变得有序。画完一遍之后代码里的每个指针作用都会清晰很多。5. 避坑指南写这道题最容易翻车的5个细节5.1 致命死循环忘记断链的后果我见过最多的错误是找完中点后没有把 mid.next 置为 null。递归排序左右两半时左半边链表的尾节点仍然指向右半边链表的头节点两个子链表在物理上是连着的。sortList 递归处理左半边时又去找中点又去递归左半边里永远包含右边的内容整个递归过程就会无限进行下去最后要么栈溢出要么超时。我记得自己第一次写这题代码逻辑看着完全没问题但提交就是 Time Limit Exceeded。后来在本地调试打印链表内容才发现递归到某一层时链表根本没变小问题就出在这条断链上。所以每次找完中点我会条件反射地写一行 mid.next null这个习惯比记任何结论都管用。5.2 边界条件空链表和单节点链表要最先处理sortList 函数的递归终止条件也就是 head null || head.next null 这一句必须放在最前面。很多人会因为题目示例里链表都至少有多个节点就忽略这个问题。但面试时面试官偏偏就喜欢递上一个空链表测你。这两个条件缺一不可head null 处理空链表head.next null 处理只有一个节点的链表。少了任何一个递归调用就可能出现空指针异常。5.3 快慢指针初始化奇偶长度的差异快慢指针找中点慢指针停在哪个位置取决于快指针是从 head 还是 head.next 出发。我在 3.1 小节里强调过推荐用 fast head.next让慢指针在偶数长度时停在左半部分最后一个节点。如果你习惯用 fast head也不是绝对不行但你要额外用一个 prev 指针记录慢指针的前驱节点然后在断链时用 prev.next null 来切分代码会多出一个变量逻辑也没那么直观。两种写法我都试过最终选择了 fast head.next 的版本因为它的断链动作最顺拿到 mid 后直接 mid.next null不需要额外记录前驱。5.4 自底向上prev指针的移动时机迭代版最容易错的地方不是 cut而是 prev 指针维护。merge 结束后prev.next 被指向合并后的链表头部但 prev 本身还停在原来的位置必须用 while (prev.next ! null) prev prev.next 把 prev 推到合并链表的末端下一轮才能继续在后面接新的合并结果。如果你漏掉这一步下一轮合并完的链表会被接到错误的位置结果就是排序后的链表七零八落。有人可能会想能不能用 prev tail 这种方式直接记录每次 merge 的尾节点理论上可以但 merge 函数返回的是头节点拿尾节点还得再遍历一遍反而不如 while 循环来得简洁。这里没有太多花哨技巧重点是别忘。5.5 常见错误速查表为了方便你自查我把几种典型错误的症状、原因和解决方案整理成一个表格错误现象可能原因解决办法提交超时疑似死循环找中点后未断链子链表仍有环加 mid.next null空指针异常未处理空链表或单节点链表函数开头加边界判断排序结果整体乱序merge 时 cur 指针忘了后移每次连接后 cur cur.next迭代版结果链表断裂prev 未移动到合并结果末尾合并后 while 推进 prev偶数长度链表切分不均快慢指针用 fast head 且未记录前驱改用 fast head.next 或记录 prev递归栈溢出链表很长但快慢指针初始化错误递归不收敛检查中点是否每次都严格靠近中心这个表格其实覆盖了我刷这道题以及看别人代码时遇到的大部分问题。你在本地写代码的时候可以把这个表贴在旁边跑测试用例之前先自己对照检查一遍。6. 面试延伸从排序链表引出的一串题目6.1 一个模板打天下相关题目清单排序链表这道题的解法里有两个函数是高频复用的merge 两个有序链表以及快慢指针找链表中间节点。这两个动作几乎是 LeetCode 链表题的“通用积木”单独拿出来都各自对应一道经典题目。合并两个有序链表LeetCode 21就是本题的 merge 函数。你把排序链表做完这道题基本等于白送。链表的中间节点LeetCode 876就是本题的 getMid 函数。注意876题没有断链的要求只要返回中间节点即可但找法的思想和本题小程序一样。合并K个升序链表LeetCode 23可以用两两合并的方式实现而两两合并的核心还是这个 merge 函数。更进阶的解法是配一个优先队列但建议先把两两合并写熟。对链表进行插入排序LeetCode 147这就是我在第1节里提到的反面教材。做完排序链表再去做147题你会对两种排序思路的差异有更直观的感受。重排链表LeetCode 143这道题需要先找中点再反转后半部分最后交错合并两条链表每一步都是前面那些题里拆出来的基础操作。很多人刷完排序链表去刷143会异常轻松因为找中点和合并这两个基本功已经被反复打磨过好几遍了。把这些题目放到一起刷你会发现所谓的“刷题”其实是在反复使用几个核心模式。当你能把 merge 和 getMid 写得不用过脑的时候链表的绝大多数难题就都有了基本骨架。6.2 再深入一点面试官还可能追问什么排序链表这道题本身不难但它上面的追问可以很有深度。我在面试中被问过两个印象很深的问题这里分享一下。第一个问题如果这道题不限制空间复杂度你会怎么做答案就是取巧方案遍历收集所有节点的 val 到数组排序再写回链表。这个方案的代码量远小于归并排序。但面试官的考察点其实是在试探你看你知不知道归并排序为什么是最优解以及能不能在限制条件下放弃“简单方案”切换思路。所以哪怕你面试时先答了取巧方案也一定要立刻补充一句这只适合没有空间限制的情况严谨的解法是归并排序。第二个问题归并排序是稳定排序吗你的 merge 函数里用小于等于会不会破坏稳定性答案是稳定的。关键在于当两个链表头部节点的值相等时我们优先取左半边的节点这样就保证了相等元素的相对位置不变。这在某些有特殊排序需求的场景中是一个实打实的加分项。刷完这道题之后我对链表题的心态变了很多。以前总想着靠背代码来应付现在更习惯先想清楚“断链之后怎么接回来”“递归到多深”这些本质问题。尤其是画图这件事我强烈建议你准备一支笔和一张草稿纸。链表题和数组题最大的不同就在于数组的索引变化是隐性的而链表的每个节点指向关系都是显性存在的不画图全靠脑补指针一旦多起来就很容易乱。我后来能把两种版本的代码都写得又快又稳核心原因就是从第一遍画图开始把每一轮断链、连接都落到实处了。最后再分享一个实用小经验面试写这题的时候如果你先写递归版可以在代码写完之后主动告诉面试官说你知道递归版本的空间复杂度是 O(log n)并可以立刻改写成 O(1) 空间的迭代版本。这一句话既证明了你对空间复杂度的敏感度又展现了你对递归和迭代两种实现掌握的熟练度效果往往比单纯把代码写对要好得多。