单向链表的节点只向前链接;反转时既要改变链接,也要保留尚未处理节点的入口。本节推导迭代算法及其不变量。
1. 前置条件与程序
定义 2.2.1
(原地反转链表的前置条件)
假设 head 是 NULL,或指向一条有限、无环链中第一个有效且仍存在的 Node。每个 next 指向链中的下一节点或 NULL。调用者允许函数修改所有链接,并确保没有与修改冲突的并发访问。节点值可重复。函数不分配、复制或释放节点;返回新的头指针。已有别名仍指向同一批活节点,但看到的链接会改变;调用者必须以返回指针作新的头。
#include <stddef.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
Node *reverse_list(Node *head) {
Node *prev = NULL;
Node *cur = head;
while (cur != NULL) {
Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
必须在改写 cur->next 之前保存 next:改写后该字段向后指,不再通往未处理的后缀。程序没有释放 cur 或 prev。若忽略返回值,调用者的旧头可能已变为尾节点,无法从它到达反转后的其余节点。
2. 循环不变量
把原来的节点依序记作 。处理了 个节点后,每次迭代开始时,,而:
prev依次指向 所成的链; 时为NULL。cur依原顺序指向 所成的链; 时为NULL。- 两链互不相交,合起来恰好包含所有原节点各一次,且各以
NULL结束。
定理 2.2.2
(链表反转的正确性与代价)
设 head 满足前置条件,原节点为 ()。则 reverse_list(head) 返回一条以 NULL 结尾的链的第一个节点,该链恰按此顺序包含 ;若 则返回 NULL。循环体恰好执行 次,函数使用 辅助空间,并且不分配也不释放任何节点。
证明
(初始、保持与终止)
初始。 时,prev 是 NULL,cur 是原链的头。保持。 若 cur 非空,先保存其下一指针,便仍能到达剩余后缀;把其链接改指 prev,就把原序列的下一节点加到反转前缀之首。更新两个局部指针后,不变量对 成立,两链仍互不相交且以空指针结束。终止。 每次迭代使未处理后缀长度减一。因 有限,cur 最终成为 NULL;此时 ,prev 是全部原节点反序所得链的头,共经过恰好 次迭代。
证明透视
为何不变量必须描述两条链
这个不变量同时谈到两条链,其中第三项承担了关键:prev 与 cur 把所有节点划分开。正是这个划分使单一的写入 cur->next = prev 安全。它只改变恰好一个节点 cur 的链接,该节点刚离开未处理的链,而该链接的旧值已先保存在 next 中。除 cur 外,两条链上的节点都没有被触动。
每个假设只在一处使用。有限性给出终止。无环且以空指针结束,用于初始情形:cur 必须是一条以 NULL 结束的链的头。节点身份互异(而非数值互异)给出互不相交的条款。证明在 时完成:未处理的链为空,所以 prev 反序持有所有节点。若没有无环这个条件,初始情形便不成立,下一个例子说明这一点。
空链返回 NULL;单节点链返回同一节点,其链接仍为 NULL。算法遍历 个节点,时间为 ,把空链固定成本一并计算可写成 ;辅助空间为 。成本分析采用这种表示法及指针操作单位成本模型,不直接推论其他表示法。
反例模式
有环的链不是一条长链
一个诱人的说法是:循环只是向前走到遇见 NULL 为止,所以对碰巧有环的链也能反转。取节点 与 ,有 a->next = b 及 b->next = a,这违反前置条件。第 1 次迭代:cur = a,next = b,令 a->next = NULL,于是 prev = a、cur = b。第 2 次迭代:next = b->next = a,令 b->next = a,于是 prev = b、cur = a。第 3 次迭代:next = a->next = NULL,令 a->next = b,于是 prev = a、cur = NULL。调用返回 ,但此时 a->next = b 且 b->next = a:返回的链永远到不了 NULL。
循环之所以停止,只是因为第一次迭代碰巧把 a->next 改成了 NULL。后置条件(以空指针结束的反转链)不成立。补救办法就是前置条件本身:证明依赖有限且以空指针结束的链;对无效输入不作声称。
3. 指针追踪
例题 2.2.3
(追踪四个节点)
对 12 -> 4 -> 15 -> 6 -> NULL,下表列出每次迭代开始时的两条链,最后一行为终止状态。这里用数值标记节点;证明使用节点身份,数值重复时也成立。
| 已处理 | prev 链 | cur 链 |
|---|---|---|
| 0 | NULL | 12 -> 4 -> 15 -> 6 -> NULL |
| 1 | 12 -> NULL | 4 -> 15 -> 6 -> NULL |
| 2 | 4 -> 12 -> NULL | 15 -> 6 -> NULL |
| 3 | 15 -> 4 -> 12 -> NULL | 6 -> NULL |
| 4 | 6 -> 15 -> 4 -> 12 -> NULL | NULL |
当 cur 成为 NULL,函数返回 prev。原本指向节点 12 的指针仍指向同一节点,但它现在是尾节点,不能代表整条反转后的链。
概念视角结构
把反转看成两个栈之间的搬移
把 prev 所指的链看作头在顶端的栈,把 cur 所指的链看作第二个栈,头同样在顶端。每次迭代从 cur 栈弹出顶端节点,再压入 prev 栈;被写入的指针只有新栈顶指向旧栈顶的链接。把所有节点从一个栈搬到另一个栈,顺序便被反转,这正是不变量的另一种说法:搬了 次后,prev 栈由顶至底为 至 。把节点搬回去就恢复原来的顺序,所以连续反转两次会得回原来的链表。
例题 2.2.4
(数值重复,节点不同)
设链为 p -> q -> r -> NULL,其中 p 与 q 的值都是 8,r 的值是 3。第 1 次迭代:next = q,p->next = NULL,prev = p,cur = q。第 2 次迭代:next = r,q->next = p,prev = q,cur = r。第 3 次迭代:next = NULL,r->next = q,prev = r,cur = NULL。调用返回 r -> q -> p -> NULL,即依次为原来第三、第二、第一个节点。两个值为 8 的节点仍是两个节点,顺序颠倒;相同数值不会使节点合并。
例题 2.2.5
(边界情形:空链与单个节点)
对空链,cur = head = NULL,循环体一次也不执行,函数返回 prev,即 NULL。对单个节点 p,循环体执行一次:next = NULL,p->next = prev = NULL,prev = p,cur = NULL。函数返回 p,其链接仍为 NULL;反转单节点链没有任何改变。这就是定理中 与 的情形。
4. 检查与练习
常见错误
(先改写链接才保存它)
若循环先执行 cur->next = prev,再读取 next = cur->next,则 next 会等于 prev。对 1 -> 2 -> 3,第一次迭代就使 cur 成为 NULL,函数只返回节点 1,节点 2 和 3 无法从结果到达。其他独立别名可能碰巧保留它们的入口,但算法不能依赖这一点。
常见错误
(丢弃返回的头指针)
对 1 -> 2 -> 3 调用 reverse_list(head) 之后,调用者的变量 head 仍指向节点 1,但它现在是尾节点,其 next 为 NULL。从 head 出发只看到一个节点的链。新的头是返回的指针,即节点 3。
快速检查
(把有效链反转两次,解释为何返回链恢复原有顺序及节点身份。)
对第一次调用的输出应用定理。
解答 · 答案
由定理,第一次调用返回有效的链 ,它同样满足前置条件。第二次调用把它反转成 。每次调用都只重新链接现有节点,不分配也不释放节点,所以同样的节点以原有顺序出现。
快速检查
(若把循环条件由 cur != NULL 改为 cur->next != NULL,对 1 -> 2 -> 3 函数返回什么?)
追踪到 cur->next 为 NULL 为止。
解答 · 答案
第 1 次迭代(cur 是节点 1):next 是节点 2,1->next = NULL,prev 是节点 1,cur 是节点 2。第 2 次迭代(cur 是节点 2,且 cur->next 是节点 3):next 是节点 3,2->next = 1,prev 是节点 2,cur 是节点 3。此时 cur->next 为 NULL,循环停止,函数返回节点 2,即链 2 -> 1 -> NULL。节点 3 从未被处理,也不在结果之中。
快速检查
(在 12 -> 4 -> 15 -> 6 的追踪中,处理了两个节点之后,prev 与 cur 各指向哪条链?)
用 的不变量。
解答 · 答案
prev 指向 ,即 4 -> 12 -> NULL;cur 指向 ,即 15 -> 6 -> NULL,与已处理 2 个节点那一行相同。