空间详解)
★ FEATURED ARTICLE LeetCode Hot 100第148题“排序链表”我前后做了至少五遍每一遍都推翻一点之前的自以为是。最初能AC就觉得已经会了后来被面试官追问“能不能把空间压到O(1)”才意识到递归版只是及格线再后来认真琢磨为什么这道题的最优解偏偏是归并排序而不是快排、堆排才算把链表排序这件事彻底想透。这道题表面上是“给一条乱序链表排序”实际一次性考完了链表操作里最核心的三板斧——快慢指针找中点、dummy节点合并有序链表、按步长切链。如果你刚刷到链表专题或者想在面试前把链表基本功打扎实这篇文章值得你花二十分钟读完如果你已经AC过建议重点看后面关于自底向上和踩坑的部分那里是大多数人容易漏掉的细节。1. 为什么“给链表排序”比给数组排序麻烦这么多这个问题我在第三遍刷的时候才认真想过。以前刷数组排序题很顺手快排、堆排、希尔排序随便挑写起来都有现成的套路。可是一到链表上这些套路全部失效或严重打折。原因不是某个排序算法本身不好而是数组这个数据结构给算法提供了太多隐性红利链表一样都给不了。1.1 数组排序里被习以为常的三张底牌第一张底牌是O(1)随机访问。数组按下标访问任意位置开销和访问第一个元素一样。快排需要随时跳转到左右两端堆排需要从下标i找到它的左孩子2i1和右孩子2i2希尔排序需要按某个gap跳着取元素这些操作在数组上都像呼吸一样自然。第二张底牌是原地交换。数组排序最重要的动作就是“换”swap两个下标对应的值不需要移动其他元素。快排的partition、堆排的建堆和调整全是建立在“我能直接把两个位置的元素换掉”这个前提上的。第三张底牌是区间的天然表达。数组可以用[start, end]两个下标描述一段连续区间分治的时候直接mid (start end) / 2左右边界清清楚楚。递归传递的只是整数开销极小逻辑上也几乎不可能出错。这三种红利在排序算法里几乎是默认配置大家写惯了数组排序潜意识里会把“二分区间”“交换元素”“按下标跳转”当作理所当然。一旦切换到链表这三张牌全部抽走很多在数组上简单的操作就会变得非常别扭。1.2 经典排序算法迁移到链表时的逐个体检先说快速排序。快排的核心是partition选一个pivot让小于pivot的都在左边大于的都在右边。数组上可以用双指针从两端向中间扫描边扫边换。单链表只有next指针想从右端往前扫根本做不到只能改成“用两个链分别收集小于和大于pivot的节点最后拼接”。思路没问题但每层partition都要完整遍历一遍链表pivot又不像数组那样可以随机选得很均匀最坏情况下递归深度变成O(n)整体还是O(n²)。而且每次递归要生成两个新链表头代码比数组版复杂得多面试时讲解也费劲。再看堆排序。堆排序在数组上几乎不需要额外空间因为堆的结构是隐式存在数组下标里的。链表的节点分布在内存各处你想找某个节点的左孩子必须从它的位置出发沿着next指针走过去——这本质上已经退化成“每次访问子节点都是O(1)”以外的操作。就算用最小堆把所有链表节点塞进去再依次弹出空间复杂度直接变成O(n)完全违背了堆排序省空间的初衷。再看希尔排序。它需要按固定增量跳跃访问元素链表上虽然可以通过走step步实现但每走一步都是O(step)整体常数极大工程上没人这么写。最后说插入排序。插入排序在链表上其实不差因为链表插入一个节点只需要改动两根指针不需要像数组那样搬移元素。但它的时间复杂度仍然是O(n²)数据规模到了10⁵量级就顶不住了。LeetCode这道题的数据范围可以到几万个节点O(n²)大概率TLE。1.3 结论归并排序为什么是链表的天选算法归并排序在这份体检里几乎全部过关。它最核心的操作是“合并两个有序链表”而合并只需要同时看两个链表的头节点谁小就取谁从头到尾顺序访问不需要随机跳转不需要交换不需要下标区间。它要的分治区间也不依赖下标——快慢指针走一遍就能把链表从中间切两半。换句话说归并排序的底层能力要求是“顺序访问”链表给得起快排和堆排要求的“随机访问”和“就地交换”链表给不起。算法和数据结构的匹配关系就是这么现实不是某个算法绝对好而是它适不适合你手上的这个结构。2. 自顶向下归并递归版完整实现想通归并是链表本命之后第一版解法就是自顶向下递归。思路和数组归并排序几乎一一对应把链表平均分成两半分别排序再合并。差别只在“怎么分”和“怎么合”。2.1 分治落地链表的两个关键动作数组分治靠下标算中点链表分治靠快慢指针。合并的时候数组要靠一个临时数组来缓存结果链表不需要额外空间直接在原节点上改next指针就能接成一条新链。这两个差异构成了链表归并的全部难点和全部魅力难在找中点和切断妙在合并时零额外空间。很多教程会把“找中点”和“合并”当成两个并列知识点但实际编码时还有一个第三动作容易被忽略——切断。只找到中点还不够如果左半段和右半段还藕断丝连后面的递归和合并会乱套。正确的步骤是先找到左半段的最后一个节点把它的next置为None让左右两半彻底分家。2.2 快慢指针找中点这样写最稳快慢指针找中点的标准做法是慢指针每次走一步快指针每次走两步快指针走到末尾时慢指针正好停在某个中点附近。问题在于“哪个中点”——奇数长度的时候慢指针恰好停在正中间偶数长度的时候慢指针停在哪取决于初始化方式和循环条件。我最推荐的是这样写slow head fast head.next while fast and fast.next: slow slow.next fast fast.next.next这套写法里fast先人一步出发。链表长度为偶数时循环结束时slow恰好停在左半段的最后一个节点上长度为奇数时slow恰好停在正中间。不管哪种情况slow.next一定属于右半段。于是右半段直接从slow.next开始再把slow.next置为None两段长度最多相差1分割非常均衡。如果把fast也初始化为head循环条件还写成while fast and fast.next遇到偶数长度时slow会滑到右半段的起点导致左半段多包含一个节点。这样最终结果不会错但分割不均衡最坏情况下递归深度退化的风险在极端输入里会出现。另一个常见错误是把循环条件写成while fast.next遇到两个节点的链表时fast会直接滑到末尾再外访问fast.next直接抛空指针异常。2.3 dummy节点合并两条有序链表合并是这道题另一个必须熟练到肌肉记忆的操作。思想很朴素用两个指针分别指向两条链的头部每次比较当前两个节点的值把较小的那个接到结果链尾部然后指针后移直到有一条链为空剩下的整段直接拼接。为什么需要dummy节点因为结果链的头节点不确定——它可能是左链的头也可能是右链的头取决于哪边的值更小。与其在循环外面做一堆if判断头节点到底是谁不如先造一个假的头节点让所有节点统一挂在它后面。循环结束后返回dummy.next既不用特判也不容易错。def merge(self, l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next这里有个小细节我一开始没注意cur cur.next必须写在if-else外面表示“本轮接到结果链上的节点已经成为新的尾部”不管选中了谁尾部都要向后走一格。如果我在每个分支里都写一遍cur cur.next逻辑上也没错但代码冗余容易漏写导致死循环。2.4 自顶向下完整代码与复杂度分析把上面两块拼起来加上递归出口就是完整的自顶向下归并排序class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head # 快慢指针找中点 slow head fast head.next while fast and fast.next: slow slow.next fast fast.next.next right slow.next slow.next None # 切断左右两半 left self.sortList(head) right self.sortList(right) return self.merge(left, right) def merge(self, l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next复杂度可以用递推式说明T(n) 2T(n/2) O(n)。找中点的快慢指针要遍历半条链合并两条链要遍历两段单层操作是O(n)递归深度是O(log n)所以总时间复杂度稳定在O(n log n)。空间上因为合并是原地改指针没有辅助数组额外空间只来自递归调用栈深度O(log n)所以空间O(log n)。有一点值得说清楚这里的时间复杂度是“稳定”的O(n log n)不会像快排那样退化到O(n²)。原因在于链表分割用的是快慢指针天然对半分不依赖pivot的质量。这算是链表归并比数组快排更让人安心的地方。2.5 为什么递归版空间是O(log n)而不是O(n)我见过有人把数组归并的O(n)辅助空间直接套到链表归并上认为这道题空间也是O(n)。这是错的。数组归并的O(n)是为了缓存两个有序子数组的合并结果链表合并不需要这个缓存——我只是把节点之间的next指针重新连接了一遍节点本身还是原来的节点没有复制。所以链表归并的空间只取决于递归深度也就是O(log n)。这个区别在面试里很值得主动讲出来能体现出你是真的理解归并排序而不是背模板。3. 自底向上归并把空间压到O(1)的迭代版递归版能AC而且代码简洁但题目进阶要求是O(1)空间复杂度。面试官大概率会在这个地方追问一句“能不能不用递归把额外空间降到常数级”如果你只准备了递归版卡在这一下就很可惜。3.1 进阶要求与递归版的空间瓶颈递归版的O(log n)空间其实已经很小但只要用了递归就必然占用系统调用栈。数据规模大到一定级别、或者递归深度因为写法问题被拉长时栈仍然是风险点。O(1)空间的解法要用迭代模拟归并也就是自底向上的归并排序——不是从整条链往下拆而是从长度为1的小段开始两两合并成2再两两合并成4直到整条链有序。3.2 步长翻倍的整体流程拆解自底向上的核心是控制一个归并步长step。第一轮step1把链表看成若干个长度为1的节点相邻的两个节点两两合并得到若干长度为2的有序段第二轮step2把这若干个长度为2的有序段两两合并得到长度为4的有序段第三轮step4以此类推。每轮结束step翻倍直到step大于等于链表长度此时整条链只剩一个有序段排序完成。这个思路比递归版更贴近“分治”的本来面目分治不一定要用递归实现只要你保证每一轮都是从左到右把相邻等长的两个有序块合并效果和递归完全一样。要在链表上实现这个流程有两个难点。第一怎么从当前链表里切出长度正好为step的两段第二合并完的结果怎么接回已经排好的尾部同时还得记住剩余部分的起点。这两件事用一个cut函数和一条主循环就能解决。3.3 cut切链函数自底向上的灵魂cut函数的作用是从head节点开始取长度为step的子链并把这条子链与后面的剩余链断开返回后半段的起点。代码很短但值得逐行看def cut(self, head, step): if not head: return None while step 1 and head.next: head head.next step - 1 rest head.next head.next None return rest“前进step-1步”是为了停在子链的最后一个节点上。比如step2从第一个节点走一步就到了第二个节点此时head.next指向第三个节点把它设为None前两个节点就独立成段了。如果链本身不足step步循环会因为head.next为空提前结束这时head就是原链最后一个节点rest自然是None处理方式完全一样。这个函数是典型的“用指针换信息”的例子它不返回子链本身因为外部早就保存了子链的起点它只负责两件事——切断子链尾部把剩余链的起点告诉调用者。3.4 自底向上完整代码与边界处理主循环的写法是这道题的精髓。每一轮迭代都要把整条链表从头到尾重新“串”一遍class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head # 先统计链表长度 n 0 p head while p: n 1 p p.next dummy ListNode(0) dummy.next head step 1 while step n: prev dummy # 上一轮已排好链表的尾部 cur dummy.next # 本轮待处理的链表头 while cur: left cur right self.cut(left, step) # 切出第一段返回第二段起点 cur self.cut(right, step) # 切出第二段返回第三段起点 prev.next self.merge(left, right) # 让prev移动到合并结果的末尾 while prev.next: prev prev.next step * 2 return dummy.next def cut(self, head, step): if not head: return None while step 1 and head.next: head head.next step - 1 rest head.next head.next None return rest def merge(self, l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next这段代码的边界情况很值得展开说。第一如果第二段不存在也就是right为Nonecut(right, step)会直接返回Nonemerge(left, None)会把left原样返回看上去这轮合并什么也没做但left已经被切断成独立的一段并且接到了prev后面后续循环会继续处理剩余部分不会死循环。第二prev每轮必须更新到当前合并结果的最后一个节点否则下一轮p.next会把上一段节点覆盖掉链表就断了。第三外层循环条件step n如果链表长度为5step会依次取1、2、4当step变到8时循环退出此时5个节点已经全部有序。这个条件不能用step n否则会多余地跑一整轮空归并。3.5 递归版和迭代版到底怎么选对比维度自顶向下递归版自底向上迭代版实现思路递归拆分成两半先排序再合并从长度为1的块开始按步长两两合并额外空间O(log n)递归调用栈O(1)只用常数个指针代码简洁度逻辑清晰写起来快需要理解cut和prev的衔接容易出错实际运行数据量小时差别不大多了一次统计链长的遍历常数略高面试推荐第一版答案容易讲清楚追问优化空间时的进阶答案我个人的建议是面试时先稳稳地写递归版讲清楚O(n log n)时间和O(log n)空间如果面试官继续追问“能不能做到O(1)空间”再切换到迭代版。两个版本都提前准备好展示出你既懂递归分治的直观也懂迭代分治对空间的控制这道题基本就稳了。4. 这题的坑我基本都踩过排查链路实录很多题是“看着答案觉得简单自己写就报错”。148题尤其如此它的坑不在算法思想上全在指针操作的细节里。下面这几个坑是我自己实际踩过、并且帮别人排查过很多次的。4.1 快慢指针初始化与循环条件的组合陷阱先说最典型的错误写法把slow和fast都初始化为head循环条件写成while fast and fast.next。这种写法在奇数长度链表上没问题但在偶数长度链表上slow最终会停在右半段的起点。比如链表[4,2,1,3]慢指针会滑到值为1的节点上左半段变成[4,2,1]右半段变成[3]。分割不均衡递归版的空间复杂度虽然理论上还是O(log n)但最坏情况下递归深度会退化。我一开始没意识到这个问题的严重性直到用超长随机链表对拍时才看到偶尔的超时波动。更严重的问题是空指针异常。写成while fast.next时如果链表只有两个节点fast初始在第二个节点fast.next为空但循环体还要执行fast fast.next.next这一步会直接访问None.next。排查这种问题最快的方法就是取一个长度为2的链表手工走一遍循环。正确的组合我已经在前面给了用fast head.next这个“错开一个身位”的初始化配合while fast and fast.next。这样无论奇偶slow都能停在左半段的最后一个节点上保证左右两段分割均衡、不重叠、不漏节点。4.2 忘记切断链表导致的死循环与资源耗尽如果找完中点后忘了写slow.next None会发生什么递归调用会继续对left和right做sortList但left的尾节点还连着right的头节点两条链根本是“你中有我我中有你”。合并时merge函数会同时遍历这两条互相纠缠的链可能出现永远到不了空指针的情况——结果就是程序疯狂空转直到卡死或内存耗尽。这种错误特别隐蔽因为小规模样例可能侥幸没触发节点一多就现形。排查方法也很粗暴在代码里每轮合并后打印当前链表长度如果长度没变或者某个段越合越长八成就是没切干净。记住一句话链表分治和数组分治最大的差别不是找中点而是找完中点必须“物理上拆开”。4.3 自底向上写法里prev指针为什么总写错自底向上的代码里最容易被忽略的是合并完成后让prev前进到段尾。很多人写完prev.next self.merge(left, right)后就直接进入下一次while循环结果下一轮开始时prev还是老位置新合并的段把上一轮已经排好的部分覆盖了链表从中间断掉。正确的做法是把prev更新到合并结果的最后一个节点。我见过两种实现一是像我上面那样用一个while prev.next循环走到尾二是维护一个tail指针在merge函数里顺便返回最后一个节点。第二种写法能少一次遍历但会让merge函数签名变复杂。实际测试下来用while prev.next的写法代码更直白虽然每次多走一遍段尾但所有轮的总体复杂度仍然是O(n log n)完全可以接受。另一个相关的小坑是每轮内层循环开始时cur必须重新从dummy.next开始。如果错误地沿用了上一轮结束后的cur值后面就会漏掉已经排好的节点甚至直接陷入死循环。4.4 递归深度和超长链表的真实风险有人担心递归版在超长链表上会爆栈这个担心要分情况。对于这道题的数据范围链表长度最多几万递归深度是log₂n大概只有十几层根本到不了Python默认递归上限。真正危险的情形是分割不均衡——如果快慢指针写错导致每次只卸下一个节点递归深度就变成O(n)几万层递归直接RecursionError。换句话说递归深度的风险不是来自选递归还是迭代而是来自你找中点写没写对。不过这题练完之后我还是更看好自底向上版。它不需要递归也就彻底不依赖语言对递归深度的容忍度在内存受限的真实环境中O(1)空间是一个实打实的优势。4.5 一个实用的调试与对拍思路我自己调试链表题有个固定套路先写一个把链表转成Python list的小函数再写一个从list重建链表的函数。排序完成后把结果转回list和直接用内置sorted对原list排序的结果对比。对拍样本生成用随机数节点数从1到几千都跑一遍基本能覆盖大部分指针边界问题。def linked_to_list(head): res [] while head: res.append(head.val) head head.next return res这个方法不是用来“作弊绕过链表排序”的而是作为验证正确性的工具。真正提交的时候一定还是要用链表操作实现排序否则就失去了刷这道题的意义。5. 从148题带走的可复用模板与后续扩展刷题最怕的是“刷一道忘一道”。148题最大的价值是它把链表操作里最常用的三个模板集中考了一遍。把这些模板单独抽出来你会发现后面的很多链表题都在重复它们。5.1 三个链表操作模板第一个模板是快慢指针找中点。这个模板在求链表中间节点、判断回文链表、重排链表里都会用到。核心是双指针错位和循环条件的匹配建议直接把fast head.next while fast and fast.next固定成肌肉记忆。第二个模板是dummy节点合并两条有序链表。合并两个有序链表这道题本身就是Hot 100的常客而且合并K个升序链表里也要反复调用它。dummy节点能省掉所有“头节点到底是谁”的特判这个习惯适用于几乎所有需要动态构建新链的场景。第三个模板是cut切链。它比前两个稍微冷门一点但作用很大按固定长度把链表切成独立段是自底向上归并、K个一组翻转链表这类题的基础。能用好cut说明你对“改next指针就是改变链表结构”这件事已经真正理解了。5.2 与148题联动的经典题目路径如果你按顺序刷链表专题我个人建议的路线是先做合并两个有序链表再做链表的中间节点然后把这两题合起来就是148的自顶向下版之后做排序链表把迭代版吃透再做合并K个升序链表感受把merge复用到多路归并的场景最后做K个一组翻转链表体会cut切链的进阶用法。这条路线的好处是每一题都在复用前面练过的模板不会出现“学了新忘旧”的问题。148题就像是这些模板的汇总考试能独立AC它说明链表基础操作已经过关。5.3 面试深挖方向为什么不是快排和堆排面试官大概率会问一个衍生问题“这题能用快排做吗”准备思路很清晰快排依赖partitionpartition在数组上靠双指针从两端扫描和交换单链表只有单向next要么改成“小链大链中间链”的三链拆分要么每层都要完整遍历实现复杂且最坏O(n²)。而链表的插入成本低反而更适合归并——这正好把问题引导回你的解法上。“为什么不能用堆排序”也是常见的追问点。数组堆排序的子节点位置靠下标计算链表没有随机访问维护堆会变成O(n)访问得不偿失如果非要用堆只能把所有节点装进额外堆结构空间O(n)不满足进阶要求。回答完这两个问题再主动补一句“链表归并的空间优势来自合并是原地改指针不需要辅助数组”面试观感会好很多。5.4 工程启示归并思想在真实场景里的身影这道题看着很“竞赛”其实归并思想在工程里随处可见。大文件排序用的外部排序就是先把大文件切成能装进内存的块块内排好序再做多路归并数据库做排序合并连接时底层也是类似的多路归并算法。链表的演化版本——比如分布在不同磁盘块上的有序段——本质上也需要这种“分段有序再逐层合并”的思路。刷题能带给工程最大的价值不是让你记住某个题的答案而是让你看到算法和数据结构之间的适配关系数组上最强的排序算法迁移到链表上可能水土不服反过来链表上最自然的归并思想在文件系统和大数据场景里依然是最底层的那根支柱。最后分享一个我个人的刷题习惯这道题的递归版和迭代版我都会在笔记里各保留一份并且标注两者的空间差异。面试被追问时我从来不需要现场想直接就能从“递归版O(log n)栈开销”讲到“迭代版为何能做到常数空间”。如果你也想彻底吃透这道题建议你也用自己的话把第3节里cut函数和prev指针的关系讲一遍——讲得出来才是真会了。
阅读完成 · 觉得有帮助？
