假设链表有限、无环、单向链接,且以顺序方式独占修改。
复习路线。 每次操作后追踪节点身份和当前位置。验证时先检查所有请求的边界,再重写任何原有链接,然后使用反转不变量。
检查清单。 反转重新连接两端,也可能改变头。无效位置需要明确处理策略。验证过程不得解引用空指针。最坏时间 和额外引用数 假设指针操作为常数时间。
1. 两次反转使用当前位置
练习
(不同节点组成链表 。先反转第 3 至第 6 个位置,再对所得链表反转第 2 至第 4 个位置。写出每次操作后的链表,并指出节点 的最终后继。)
核心
提示(1)
先写出第一次反转后的链表,再选择第二次操作的节点。
解答(3)
- 1
反转第 3 至第 6 个位置
第一段为 ;反转后得到 。
- 2
在新链表中读取第二次的位置
关键一步
新链表的第 2 至第 4 个位置是 。第二次操作不再使用原链表中的位置。
依据: 第二次操作作用在它所收到的链表上。
- 3
反转并读出后继
反转 得到 。因此 的最终后继为 。
2. 拒绝无效位置且不改变链表
练习
(扩展教学算法,使其在有限无环链表(包括空表)上接受任意整数位置 。如果位置无效,返回 error 且不改变任何原有 next 字段。准确描述验证过程并给出最坏时间和辅助空间。对于 和 ,给出结果。)
核心
提示(1)
在写入任何原有链接之前,先完成所有检查。
解答(5)
- 1
立即拒绝不可能的整数
若 或 ,返回
error。 - 2
带空值检查地走到前驱
令
dummy.next=head、before=&dummy。重复 次:若before.next为空,返回error;否则令before=before.next。 - 3
带空值检查地走到片段之后的节点
令
after=before.next,重复 次:若after为空,返回error;否则推进after=after.next。若初始为空表,即使 也会在这里失败。 - 4
验证成功后才反转
关键一步
使用
first=before.next和算出的after,执行教学正文的反转循环,然后赋值before.next并返回dummy.next。验证期间不写入原有链接,所以被拒绝的输入保持不变;dummy 只写临时记录。依据: 验证只读取链接,从不写入原有链接。
- 5
检查例子与代价
对于 和 ,验证到达 ,依次经过 和 ,还未完成四次推进就遇到空值,因此返回
error, 保持不变。输入有效时,验证和反转合共使用 时间和 辅助引用;输入无效时,初始检查或某次遍历遇空值停止,因此在整数和指针操作为常数时间的模型下,界相同。输入无环的假设仍然必要。
快速检查
(反转有效链表的第 至第 个位置,再对同样的第 至第 个位置反转一次。最终的链表是什么?)
第一次反转后,第 至第 个位置上是哪些节点?
解答 · 答案
原来的链表。第一次反转只是重排第 至第 个位置内的节点,所以这些位置上仍是同一批节点;再反转一次便还原。对 和 ,链表依次是 ,然后又回到 。
要避免的错误
反例模式
一边验证一边重写
一个诱人的设计是先反转片段,在循环中途遇到空值才报告 error。对 和 ,取 prev=null 并从 开始。第 1 次迭代令 B.next=null;第 2 次令 C.next=B;第 3 次 curr 为空,程序返回 error。但链表已不再是 :A.next 仍是 ,而 B.next 为空, 指回 ,所以从头无法到达 。约定要求返回 error 时链表不变。补救办法是在写入任何原有链接之前完成所有检查。
常见错误
(在原链表中读取第二次操作的位置)
若把第二次操作套用在原链表 的第 2 至第 4 个位置,会选到 。在第一次操作后的链表 中,这几个节点分别位于第 2、6、5 个位置,根本不构成一个片段。第二次操作必须使用它所收到的链表中的位置。