你好，同学。欢迎来到 NOI 专题训练营。今天我们要挑战的是一道非常经典且基础的题目——反转链表。虽然在 LeetCode 上它是简单难度，但在 NOI 的赛场上，链表操作是构建高级数据结构（如跳表、块状链表、Splay 树的辅助结构等）的基础。

请拿出你的草稿纸和笔，我们开始。

---

一、 题目描述 (NOI 风格)

【题目名称】 反转链表 (Reverse Linked List) 【时间限制】 1.0s 【内存限制】 256MB

【问题描述】 给定一个单链表的头节点 head，请你反转该链表，并返回反转后的链表头节点。 在 NOI 竞赛中，通常要求你对内存管理有精确的控制。虽然本题主要考察逻辑，但请思考如何在 $O(n)$ 的时间复杂度和 $O(1)$ 的额外空间复杂度内完成任务。

【输入格式】 输入包含一行或多行，表示链表各节点的值。 （注：在标准的 NOI 题目中，通常先输入节点总数 $n$，再输入 $n$ 个整数。为保持与原题一致，假设 $n$ 在 $[0, 5000]$ 范围内。）

【输出格式】 输出反转后的链表序列。

【样例 1 输入】

1 2 3 4 5

【样例 1 输出】

5 4 3 2 1

【样例 2 输入】

1 2

【样例 2 输出】

2 1

【数据范围】

• 链表中节点的数目范围是 [0, 5000]。
• -5000 <= Node.val <= 5000。

---

二、 预备知识点

1. 链表结构 (Linked List)：理解指针（或动态内存）如何将散落在内存中的节点串联起来。
2. 指针操作：掌握 p->next 的含义，特别是如何断开连接并重新指向。
3. 迭代与递归 (Iteration & Recursion)：这是解决算法题的两大核心思维。
4. 边界处理：处理空链表和只有一个节点的特殊情况。

---

三、 启发式教学：草稿纸上的推理过程

1. 图形化思考 (可视化思维)

想象你手里有一串珠子，每颗珠子都有一个钩子指向下一颗。 [1] -> [2] -> [3] -> NULL

目标： 变成 NULL <- [1] <- [2] <- [3]。

痛点思考： 当你把 [2] 的钩子从 [3] 断开，转而指向 [1] 时，你会发现——你丢了 [3] 的地址！ 后面的珠子都掉进虚无里了。

2. 步骤推演 (草稿纸步骤)

方法 A：迭代法（双指针/三指针） 我们需要三个身份：

• prev (前任)：指向已经反转好的链表头。
• curr (现任)：当前正在处理的节点。
• nextTemp (临时备胎)：用来预存 curr 的下一个节点，防止丢失。

请你在草稿纸上模拟：

1. 初始状态：prev = NULL, curr = head。
2. 第一步：nextTemp = curr->next (记住后面还有谁)。
3. 第二步：curr->next = prev (反戈一击，把钩子往回指)。
4. 第三步：prev = curr, curr = nextTemp (全体向后挪一步)。
5. 重复，直到 curr 为空。

方法 B：递归法（分治思维） 如果你已经能反转 head->next 之后的所有节点，你怎么把 head 接上去？

1. 假设 reverseList(head->next) 已经把 2->3->4 变成了 4->3->2。
2. 此时 head 是 1，而 head->next 指向的是 2。
3. 你需要让 2 指向 1：head->next->next = head。
4. 记得切断 1 原有的指向：head->next = NULL。

---

四、 算法流程图 (伪代码提示)

我们将逻辑转化为逻辑流程，请注意在 NOI 中，指针的安全检查非常重要。

1. 迭代法逻辑

graph TD
    A["开始反转"] --> B{"curr 是否为空?"}
    B -- "否" --> C["1. 暂存: nextTemp = curr->next"]
    C --> D["2. 转向: curr->next = prev"]
    D --> E["3. 移动: prev = curr"]
    E --> F["4. 推进: curr = nextTemp"]
    F --> B
    B -- "是" --> G["返回 prev (新表头)"]

2. 递归法逻辑

graph TD
    Start["递归入口"] --> Check{"head 或 head->next 是否为空?"}
    Check -- "是 (递归边界)" --> ReturnSelf["返回 head"]
    Check -- "否" --> Recurse["递归调用: newHead = reverse(head->next)"]
    Recurse --> Connect["让原下一个节点指向自己: head->next->next = head"]
    Connect --> Break["断开原连接: head->next = NULL"]
    Break --> Final["返回 newHead"]

---

五、 复杂度分析与优化建议

• 时间复杂度：

  • 迭代法：遍历一次链表，$O(n)$。
  • 递归法：每个节点访问一次，$O(n)$。
  • 优化建议：在 $n=5000$ 的规模下，$O(n)$ 已经是最优解，无法进一步降低阶数。

• 空间复杂度：

  • 迭代法：只使用了常数个额外指针，$O(1)$。
  • 递归法：由于递归调用会占用系统栈空间，深度为 $n$，因此是 $O(n)$。
  • 竞赛技巧：在 NOI 比赛中，如果内存限制非常严苛（如 64MB），且 $n$ 很大，应优先选择迭代法以避免栈溢出（Stack Overflow）。

---

六、 读题关键词总结

在 NOI 题目中，看到以下关键词要提高警惕：

1. “反转/逆置”：通常暗示需要改变拓扑结构，注意不要只打印不修改（除非题目只要求输出）。
2. “原地 (In-place)”：明确要求额外空间复杂度为 $O(1)$。
3. “单向”：意味着你无法通过 node->prev 回头，必须在遍历时自行维护前驱指针。
4. “$0 \le n$”：注意链表为空的坑点，这是很多选手在样例过掉后被系统测出 Segmentation Fault 的原因。

教练寄语：链表题是练手感最好的题目。请尝试在不看任何代码的情况下，在纸上把那三个指针的挪动过程画三遍，直到你闭上眼都能浮现出那个“存、指、移”的节奏。加油！

labuladong的递归解法