反转整个链表会改变头指针。只反转中间片段还有两个任务:把前驱重新连到片段的新头,并把原头连到不变的后缀。写代码前先画指针图,可以看清这两个任务。
本章扩展课程的指针、内存与结构体和作为递归 ADT 的链表材料。原地指针算法是推导应用,不表示函数式 ADT 必然使用修改操作。
约定与算法
定义 2.3.1
(片段反转的约定)
输入为有限、无环的单链表,含 个不同节点。每个节点有 next 引用和一个值。位置从 1 开始,满足 。反转第 到第 个位置上的节点;保留片段以外的节点、值和顺序。返回可能改变的头指针。操作期间不分配或释放节点;临时 dummy 记录除外,它不是返回链表中的节点。假设有独占权限修改片段节点的 next 字段,以及在 时修改前驱的 next 字段;外部节点别名仍指向原节点,但可能观察到这些字段的变化。
reverseSegment(head, l, r): # 前提:1 <= l <= r <= n
dummy.next = head
before = 指向 dummy 的引用
重复 l-1 次:
before = before.next
first = before.next
after = first
重复 r-l+1 次:
after = after.next
prev = after
curr = first
当 curr != after:
next = curr.next
curr.next = prev
prev = curr
curr = next
before.next = prev
返回 dummy.next
dummy 是带 next 字段的临时记录。当 时,before 指向 dummy,因此同一最终赋值可更新返回的头。当 时,after 为空;令 prev = after,使反转后原片段头以空引用结尾。指针 after 在改变链接之前找到。重写 curr.next 前先保存变量 next,因此未处理部分仍可访问。
为什么恰好反转所需节点
定理 2.3.2
(片段反转的正确性)
设链表由互不相同的节点 组成,且 。则 reverseSegment(head, l, r) 返回链表 的头,不分配也不释放任何链表节点。它作 次指针步骤,并使用 个辅助引用。
证明
(片段已反转前缀的不变量)
把原片段写成 ,其中 、,之后是不变的后缀,从 after 开始。经过 次迭代,:当 时,prev 指向链 的头;当 时,它等于 after。若 ,curr 指向 ,未处理的链接仍经过 到达 after;若 ,则 curr == after。
起初 ,不变量成立。一次迭代保存下一个未处理节点,使 指向已反转前缀,再推进两个引用。这样已反转前缀恰好多一个节点,同时保留剩余链。 时循环停止,prev 指向 。赋值 before.next = prev 把不变的前缀连接到该链。因此每个原节点在返回链表中恰好保留一次,后缀也得以保留。节点 从不被写入,只有 before.next 被赋值一次;从 after 起的后缀只被读取,所以返回的链表恰好就是定理所述的链表。
循环期间,从旧头能到达的链表未必已是最终链表;curr 和 prev 是必需的工作引用。并发读者观察中间链接不属于这一顺序执行约定。
证明透视
未处理节点靠什么保持可达?
第一次重写后,沿原片段头前进会到达保存的后缀,而不是剩余片段。局部引用 curr 保留了下一个未处理节点。同时 prev 的链以 after 结尾,因此循环结束时原片段头已连回不变的后缀;最后一次赋值只负责重新连接前驱。
例题
例题 2.3.3
(反转五个节点的中间片段)
不同节点 中,令 。前驱为 ,first 是 ,after 是 。起初 prev=E、curr=B。三次迭代依次建立 B -> E、C -> B -> E、D -> C -> B -> E;此时 curr 已到 。最后令 A.next=D,返回链为 。后缀从同一个节点 开始,而非从它的值的副本开始。
例题 2.3.4
(从头部开始的片段)
对互不相同的节点 ,令 、。此时 before 是 dummy,first 是 ,after 是 。起初 prev=C、curr=A。第 1 次迭代:next=B,A.next=C,prev=A,curr=B。第 2 次迭代:next=C,B.next=A,prev=B,curr=C,等于 after,循环停止。令 dummy.next=B 并返回,得到 。调用者原来的 head 即 现在是第二个节点,所以调用者必须使用返回的头。
例题 2.3.5
(边界情形:到尾部结束的片段与单个节点的片段)
取 ,、。此时 before 是 ,first 是 。找 after 要从 走三步:、,然后是空。所以 prev 起初为空。循环依次令 、、,结束时 curr 为空,等于 after。然后 A.next=D 得到 :片段原来的头 现在成为链表的结尾。
再取 ,。此时 first=B、after=C、prev=C。唯一一次迭代令 B.next=C、prev=B、curr=C。赋值 A.next=B 没有任何改变:反转单个节点的片段,结果就是它自己。
要避免的错误
常见错误
(像反转整个链表那样把 prev 设为空)
像反转整个链表那样使用 prev = null,会切断后缀。对 ,、,第一次迭代令 B.next=null,最终链表是 ,节点 丢失了。把 prev 起初设为 after,才能把片段原来的头重新连到后缀。
常见错误
(忘记最后的重新连接)
若没有 before.next = prev,前驱仍指向片段原来的头。对 ,、,反转后的链 存在,但 A.next 仍是 ,而 现在是 。结果是 ;节点 和 无法从头到达。
反例模式
超出末端的位置并非无害
一个诱人的说法是:既然寻找 after 只是走到空为止, 的位置只会反转到末端。取 ,、。此时 first 是 ,寻找 after 要走 步:第一步到 ,第二步到空,第三步要读取 null.next。这段遍历在任何链接被改变之前就已失败。
是约定的一部分。要检查它,必须先数节点个数,这是额外的工作,也是另一份约定。
代价与限制
定位 before 和 after 需要 次指针步骤;反转需要 次迭代,所以总时间为 ,最坏为 。算法使用 个辅助引用,不计已有链表。这些界假设指针操作为常数时间且位置有效;检查任意无效位置或检测输入环需要单独约定,并可能需要额外工作。值不必互不相同,因为片段由位置和节点身份决定,而非值是否相等。
习题与解答
快速检查
(对 及 ,算法返回什么?)
first 是哪个节点?after 又是哪个?
解答 · 答案
链表不变,仍是 。此时 first 是 ,after 是 。唯一一次迭代令 C.next=D,所以 prev 是 ,而 B.next=C 恢复原有的链接。反转单个节点的片段,结果就是它自己。
快速检查
(对 、、,定位 before 和 after 共需几次指针步骤?循环迭代几次?)
分开计算两次搜索的步数。
解答 · 答案
定位 before 需要 步,由 dummy 走到 。定位 after 需要 步,由 走到 。合计 步。循环执行 次。
快速检查
(为何函数返回 dummy.next 而不是 head?)
时,原来的头会怎样?
解答 · 答案
时,原来的头是被反转片段的第一个节点,反转后它不再是第一个。最后的赋值把新的第一个节点存入 dummy.next。在 、、 的例子中,head 是 ,但正确的结果是 。