p9（13 分钟）、p10（14 分钟）、p11（9 分钟）
反转不是移动数据
反转不能靠搬数据——不能把地址 102 的那个值挪到地址 250 去，只能调整链接。
输入链表 4 个节点（地址 100 / 200 / 150 / 250），输出应是：
head 指向地址 250 的节点走向 250 → 150 → 200 → 100且地址 100 的节点地址字段为 0 / 空关于 head 的措辞要抠一下：叫 head 的这个变量只是一个指针，并非头节点本身。除了头节点的地址，链表没有别的标识。
迭代反转
两个关键观察
① 如果断开了当前节点的链接，怎么去到下一个节点？ → 在设置当前节点的链接字段之前，先把下一节点的地址存到另一个临时变量里
② 在链表中，我们总是知道下一个节点的地址，但永远不会知道上一个节点的地址 → 遍历时必须用另外一个变量来跟踪前一个节点第一条是「先存后断」的由来，第二条是为什么要 previous 变量。
代码
current = head;previous = NULL; /* 头节点的前一个节点为空 */
while (current != NULL) { next = current->next; /* ① 先保存下一个节点地址 */ current->next = previous; /* ② 反转链接 */ previous = current; /* ③ previous 移到 current */ current = next; /* ④ current 移到 next */}
head = previous; /* 循环结束时 previous 存的是最后一个节点地址 */四行的顺序不能变，尤其是 ①②：先存 next，再改 current->next，否则就丢链了。
变量名 next 的歧义
next 是反转函数里的局部变量；而 current->next 这种表述指的是节点里的链接字段；单说 next 时，指的就是那个局部指针变量。两者是不同的东西，读代码时要注意。
边界测试
实现要能过所有用例，尤其要针对特殊和极端的用例验证。
① 链表为空（head == NULL）② 链表仅有一个节点结论：这两种情况这个实现都能奏效。
完整程序
这个版本里 head 是 main 的局部变量，所以：
reverse函数以头节点地址作为参数，并返回反转后的头节点地址insert函数同样接收两个参数（头节点地址 + 待插入数据），并返回头节点地址（该地址可能被修改，也可能未被修改）
演示：初始链表 2 4 6 8 → 打印 2468 → 反转 → 打印 8642。
单元素测试：注释掉三条插入语句后运行，也能跑通。
递归打印
这里写了两个函数：
print(head)：正序打印（元素以空格分隔）reverse_print(head)：逆序打印元素
注意这里不反转列表，只是按相反的顺序打印元素。这是和 p11 的关键区别。
print 实现
void print(struct node *p) { if (p == NULL) return; /* 递归退出条件 */ printf("%d ", p->data); /* 先打印当前节点 */ print(p->next); /* 再递归下一个节点 */}递归最不能忘的是退出条件。递归不能无休止地调下去，这里 p 最终会等于 NULL，到那一步就不再递归调用，直接退出。
reverse_print 实现
只改一处：不是先打印再递归，而是先递归、等递归调用结束后再打印。
void reverse_print(struct node *p) { if (p == NULL) return; reverse_print(p->next); /* 先递归到底 */ printf("%d ", p->data); /* 回溯时打印 */}递归树
print(100) → 打印 → print(200) → 打印 → print(150) → 打印 → print(250) → print(NULL) ↑ 触达退出条件这种画出来的结构叫递归树。
逆序版：先一路递归到 NULL 才返回，然后从 print(250) 开始打印（4），再 print(150) 打印（5），再 6、2。
内存模型
所有函数调用执行的细节以及局部变量 → 栈区通过 malloc / new 分配的任何内存 → 堆区链表中节点的内存是从堆中分配的 → 这 4 个节点位于堆中每次调用一个函数，都会从栈中为该函数的执行分配一定量的内存，这块内存叫那个函数的栈帧。
每次递归调用都会相应地分配一个栈帧。一个函数调用自己，和它调用另一个函数没有什么不同。栈顶的那个调用在执行。
常规遍历用递归不划算
常规遍历、常规打印，迭代方法会比递归方法高效得多。
理由：
迭代方法只会使用一个临时变量而递归中针对如此多的函数调用，我们会在内存的栈区占用空间→ 所以那里存在着对内存的隐性使用逆序打印就不一样了：反正总得把元素存储在某种结构里，所以用递归也还行。
所以结论是：
| 场景 | 更优方案 | 原因 |
|---|---|---|
| 常规正序打印 / 遍历 | 迭代 ✓ | 递归有栈帧的隐性内存开销 |
| 逆序打印 | 递归可以接受 | 反正总得把元素存进某种结构 |
这条容易写反，以为递归「更优雅所以更好」。结论是迭代更高效。
递归反转
p10 只是逆序打印，没有反转链表；这里才是真反转。
逻辑来源
直接借用了 p10 的反向打印递归函数——递归提供了一种在 C/C++ 程序中逆向遍历链表的方式。
核心想法：递归先让我们正向遍历一遍列表，然后再反向遍历一遍。
实现
前提是 head 为全局变量，这样所有函数都能访问它。
void reverse(struct node *p) { if (p->next == NULL) { /* 退出条件：最后一个节点 */ head = p; /* 修改头指针指向最后一个节点 */ return; } reverse(p->next); /* 先递归到底 */
/* 回溯时执行这三行 */ struct node *q = p->next; q->next = p; /* 反向链接 */ p->next = NULL; /* 断开 p 原来的正向链接 */}关键理解
当 reverse(250) 完成的时候，直到 250 的节点已经反转了：head 正指向这个节点，而且此节点的链接部分被设为空。等来到 150 时，可以确定列表直到 150 都已反转。
也就是说回溯过程中，每次调用结束时，从尾部到当前节点的这一段已经反转完成。
逐步走一遍
reverse(100) → reverse(200) → reverse(150) → reverse(250) → P 是 250，p->next == NULL，进入退出条件 → head = 250，对 250 的调用结束→ 回到 reverse(150)：P = 150 → q = P->next = 250 → q->next = P （把 250 的 next 设为 150） → P->next = NULL → reverse(150) 结束，此时 head=250，250→150，150→空 ✓→ 同理 reverse(200) 结束后到 200 反转→ reverse(100) 结束后整体反转，返回 main两个补充
① 语法糖 / 等价写法
q = p->next;q->next = p;可以合成一行：
p->next->next = p;意思是一样的，只不过这种表述更让人混淆。
② head 非全局时
这个反转函数就得返回修改后 head 的地址。
三种链表操作的复杂度
| 操作 | 时间 | 空间 |
|---|---|---|
| 迭代反转 | O(n) | O(1) ✓ |
| 递归反转 | O(n) | O(n)（栈帧） |
| 迭代打印 | O(n) | O(1) ✓ |
| 递归打印 | O(n) | O(n)（栈帧） |
坑
- 迭代反转的四行顺序不能变：先存 next → 改链接 → 移 previous → 移 current。
previous初值是 NULL，这样第一个节点反转后才指向空。next（局部变量）和current->next（节点字段）是两回事，读代码时别混。- 常规遍历用递归是低效的，递归有栈帧的隐性内存开销；只有逆序打印用递归才划算。
- 递归反转的退出条件是「最后一个节点」（
p->next == NULL），不是「p == NULL」。
请输入编辑凭据，只有站点所有者可以修改文章。