合并两个有序链表是一个小算法,却要履行多项义务:它必须把值按顺序排列,恰好保留每个节点一次,并使结果以 null 结尾。
1. 稳定的破坏性合并
定义 18.1.1
(稳定的破坏性合并)
假设有两个互不相交、有限、无环的单链表,均按键值非递减顺序排列。每个节点包含一个键和 next。合并过程可以重新链接输入节点:调用者此后不得再把原来的链表头当作独立链表使用。相等的键可能属于不同的节点。为使合并稳定,当两个表头的键相等时,先选择左链表中的节点;除此之外,不改变任一输入链表内部的顺序。
merge(left, right):
dummy.next = null
tail = dummy
while left != null and right != null:
if left.key <= right.key:
chosen = left; left = left.next
else:
chosen = right; right = right.next
tail.next = chosen
tail = chosen
if left != null: tail.next = left
else: tail.next = right
return dummy.next
dummy 是一个临时哨兵,不是输出中的数据节点。要通过推进相应的输入指针来保存后继节点,且必须在后续迭代覆盖任何链接之前完成。在下一次赋值之前,旧的 tail.next 仍可能指向某个输入后缀,因此在循环期间只读取输出直到 tail 为止;它还不是一个独立的、以 null 结尾的链表。
定理 18.1.2
(破坏性合并的正确性与代价)
设 left 与 right 是互不相交、有限、无环的单链表,分别有 与 个节点,且都按键值非递减顺序排列。则 merge(left, right) 返回一个以 null 结尾的链表,其中两个输入的每个节点恰好出现一次,并按键值非递减顺序排列。每个输入的节点保持输入时的顺序,而且每个左节点都排在键值相等的右节点之前。当 时,合并至多作 次键比较,否则不作比较;它需要 时间和 的辅助指针空间(不计输入节点)。
证明
(关于输出前缀与两个后缀的不变量)
把至今已移动的节点称为已选中节点。每次检验循环条件时,下列各项成立。(i) 从 dummy 沿 next 走到 tail,恰好按选中顺序访问所有已选中节点。(ii) 这段前缀上的键非递减,并且每个键都不大于每个非 null 的剩余表头的键。(iii) left 与 right 指向两个输入未被触动的后缀,两者仍互不相交,也仍然有序。
初始时没有选中任何节点,tail 是 dummy,两个后缀就是整个输入。设循环体执行一次。由于各后缀有序,两个表头中较小者不大于两个后缀中所有剩余的键。无论选了哪个表头,被选的都是那个较小者(相等时取左),所以把它接上便保持 (ii)。被选中的输入指针先行推进,因此下一次迭代覆盖 tail.next 时,该后缀的其余部分不会丢失;(i) 与 (iii) 得以保持。
当其中一个输入指针为 null 时循环结束。每次迭代移走一个节点,而另一个链表在该次迭代中非空,所以另一个后缀至少剩下一个节点。该后缀有序,由 (ii) 其键不小于前缀中的每个键,并且因输入有限且无环,它以 null 结尾。一次赋值就把它接上,所以结果以 null 结尾;节点是逐个从互不相交的链表移出的,所以每个节点只出现一次。每个输入的节点都从前端取走,所以各输入保持其顺序。
关于稳定性:只有当 严格成立时,才会选右表头而不选左表头。左后缀有序,所以此时没有剩余的左节点与该右节点键值相等。因此键值为 的每个左节点,都先于任何键值为 的右节点被选中。
当 时至多迭代 次,每次做 的工作,最后的接上也一样。额外存储只有 dummy、tail、chosen,为 。
证明透视
不变量必须描述链接,而不只是键
这个不变量同时谈到三件事:输出前缀的键、前缀上的节点身份,以及两个输入后缀的状态。每个假设只在一处使用。输入有序,只用来得知较小的表头比自己那个链表里所有剩余节点都小。互不相交,用来说明每次迭代都恰好从一个后缀移走一个节点,并使两个后缀保持互不相交。有限与无环只在最后使用,以得知被接上的后缀以 null 结尾。
唯一微妙之处是覆盖。下一次迭代会给 tail.next 赋值,取代原本通向被选节点所在链表其余部分的指针。这没有问题,因为输入指针已在同一次迭代中推进,后继节点已经保存。
当其中一个表头为 null 时,论证就完成了:不变量已说明前缀有序,且不大于所有剩余节点,所以剩余后缀可以整段接上,无需再作比较。
这些假设在实际中很容易被违反。
反例模式
共享节点使合并产生环
设 left 为 1a -> x,right 为 2c -> x,其中 x 是同一个键为 5 的节点,且 x.next 为 null。两个链表共享节点 x。循环先选 1a(因 ),再选 2c(因 ),此时 left 与 right 都等于 x。现在 ,所以 chosen = x、left = x.next = null、tail.next = x,循环结束。最后的分支令 tail.next = right,即 x,于是 x.next = x。输出是 1a -> 2c -> x -> x -> ...,永远到不了 null。
失败源于输入链表互不相交这个假设:共享节点从两边各被选中一次,第二次选中把它链回自身。修补办法是遵守这个前置条件,而不是修补循环。
常见错误
(在合并中使用严格比较)
若循环改用 left.key < right.key 而不是 left.key <= right.key,键值相等时会先取右链表的节点。左为 2a、右为 2c 时,输出是 2c -> 2a。有序性没有改变,但排序不再稳定。
例题 18.1.3
(两个链表之间有相等键的合并)
设左链表为 1a -> 3a -> 3b,右链表为 2c -> 3c -> 5c,其中字母用来标识节点。先选 1a(1 对 2),再选 2c(3 对 2)。接着两个表头是 3a 与 3c,键值相等,所以选左节点 3a;然后 3b 对 3c 又是相等,所以选 3b。左链表此时已空,剩余的 3c -> 5c 不经比较直接接上。最终的链为 1a -> 2c -> 3a -> 3b -> 3c -> 5c -> null。共作 4 次比较,不超过 。
值被正确排序,六个节点身份各出现一次,相等的键保持了左先于右的顺序。稳定性所要求的,不仅仅是返回正确的键值序列。
2. 拆分与排序
定义 18.1.4
(快慢指针拆分)
链表归并排序把含 个节点的链表拆分成两个更短的连续链表,分别递归排序,再将它们合并。拆分使用一个从表头出发的慢指针和一个从第二个节点出发的快指针。当 fast 和 fast.next 均非 null 时,慢指针前进一步,快指针前进两步。保存 right = slow.next,然后令 slow.next = null。左半部分从原表头到 slow,右半部分从 right 开始。空链表和单节点链表是基本情形。
定理 18.1.5
(拆分、链表归并排序的正确性与代价)
当 时,拆分产生两个互不相交、以 null 结尾的链表,节点数分别为 与 ,保持原有顺序,合起来恰好包含每个节点一次。链表归并排序返回同样的 个节点,按键值非递减顺序排列,并且是稳定的。它需要 时间,递归栈为 ,并重用链表节点。
证明
(计算指针步数,再对长度归纳)
把节点编号为 。循环迭代 次后,slow 在位置 ,fast 在位置 ,超出 的位置表示 null。循环恰在 fast 与 fast.next 都存在,即 时再执行一次。因此它在 次迭代后停止,此时 slow 在位置 。在 slow 之后截断,左链表有 个节点,右链表有 个节点,因为 。两者都严格短于 。
对长度归纳。长度不超过一的链表已有序。当 时,两半都更短、互不相交、有限且无环,所以由归纳假设,两次递归调用返回有序、且恰好由各自节点组成的链表。合并定理适用,给出包含全部 个节点的有序链表。
关于稳定性:设键值相等的节点 在输入中先于 。若两者在同一半,递归调用与合并都保持它们的顺序。否则 在左半、 在右半,而合并把左节点排在右节点之前。
关于代价:在递归深度 ,各子链表划分这 个节点,每个至多有 个节点。拆分含 个节点的链表约需 步,合并需 ,所以每一层花费 。当 时,子链表只含一个节点,所以有 层、时间为 。递归栈每层一个栈帧,共 。
概念视角结构
稳定性是键与位置上的次序
把节点按输入次序编号为 。稳定排序所返回的节点次序,恰好是按数对 的字典序递增排列。这些数对全都不同,所以这个次序是唯一的。对 4a -> 1b -> 3c -> 2d,数对为 ,排序后得到 1b, 2d, 3c, 4a。每次合并在键相等时优先取左边的节点,就是在遵守位置这一分量。
例题 18.1.6
(拆分并排序四个节点)
对于 4a -> 1b -> 3c -> 2d,拆分得到 [4a,1b] 和 [3c,2d]。对两半分别排序得到 [1b,4a] 和 [2d,3c];合并时比较 1 与 2(取 1b)、4 与 2(取 2d)、4 与 3(取 3c),再接上 4a,得到 [1b,2d,3c,4a]。终止性由子链表变短得出。由归纳法,每个返回的半部分都是有序的,并且恰好包含其原有的节点;再由合并的论证即可得到整个链表的结论。由于拆分保持输入的连续顺序,并且相等时偏向左半部分,整个排序是稳定的。
例题 18.1.7
(边界情形:空输入与奇数长度)
若 left 为 null 而 right 为 2a -> 4a,循环体不执行。因为 left 为 null,最后的分支令 tail.next = right,函数返回 dummy.next,即 2a。若两个输入都是 null,同一分支把 dummy.next 设为 null,结果为 null。
现在拆分 5a -> 4b -> 3c -> 2d -> 1e。慢指针从 5a 出发,快指针从 4b 出发。fast 与 fast.next 都存在,所以慢指针移到 4b,快指针移到 2d。两者再次都存在(2d 与 1e),所以慢指针移到 3c,快指针前进两个节点成为 null。循环停止。保存 right = 2d 并截断 3c.next,得到 5a -> 4b -> 3c 与 2d -> 1e,大小为 与 ,与定理的预测一致。必须先保存 right 再截断,下一个方块会说明原因。
常见错误
(在保存右半部分之前先截断链表)
若拆分先令 slow.next = null,再读取 right = slow.next,读到的是 null。对于 4a -> 1b -> 3c -> 2d,慢指针停在 1b;先截断会使 right 为 null,节点 3c 与 2d 就丢失了。
合并本身只使用常数个辅助指针,所以上面的栈界只来自排序的递归。另一种每次调用递归合并一个节点的实现可能需要 O(n) 的合并栈深度,因此其空间复杂度结论必须另行分析。
3. 习题与解答
快速检查
(合并左链表 2a -> 2b 与右链表 2c。给出结果及键比较次数。)
相等时一律偏向左链表。
解答 · 答案
表头 2a 与 2c 相等,所以选 2a。接着 2b 对 2c 又相等,所以选 2b。左链表已空,接上 2c。结果是 2a -> 2b -> 2c,共作 2 次比较。
快速检查
(合并 1a -> 3a -> 5a 与 2b -> 4b 要作多少次键比较?对长度为 3 与 2 的链表,最多可以有多少次?)
数一数迭代到其中一个链表为空为止的次数。
解答 · 答案
比较依次是 1 对 2、3 对 2、3 对 4、5 对 4,共 4 次,之后右链表已空,接上 5a。一般的界是 ,所以这个输入达到最大值。
快速检查
(用快慢指针拆分六个节点的链表 n1 -> n2 -> n3 -> n4 -> n5 -> n6。两半各含哪些节点?)
追踪慢指针与快指针的位置,直到循环条件不成立。
解答 · 答案
慢指针从 n1 出发,快指针从 n2 出发。fast 与 fast.next 都存在,所以慢指针移到 n2,快指针移到 n4。两者再次存在,所以慢指针移到 n3,快指针移到 n6。此时 fast.next 为 null,循环停止。右半部分从 n4 开始,所以两半是 n1 -> n2 -> n3 与 n4 -> n5 -> n6,大小都是 。
快速检查
(为什么拆分必须在 slow 处截断,而不能只记录 right = slow.next?)
想一想对左半部分的递归调用看到的链表是否更短。
解答 · 答案
若不截断,左半部分仍链到右半部分,两个链表并不互不相交,左链表也没有变短。对两个节点的链表,左侧调用会再次收到两个节点,递归永远到不了基本情形。