【算法】小白也能懂 · 第 3 节：链表反转（迭代法、递归法）

链表反转是面试中出镜率最高的算法题之一，也是理解链表操作的最佳练习。这一节我们会用两种方法来实现：迭代法和递归法，并配合图解帮你真正搞懂每一步在干什么。

1. 什么是链表

在正式开始之前，先快速回顾一下链表的结构。
链表由一系列"节点"组成，每个节点包含两部分：

• 存储的数据（val）
• 指向下一个节点的指针（next）

structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};

假设有一个链表1 → 2 → 3 → nullptr，反转后的结果是3 → 2 → 1 → nullptr。本质上就是把每个节点的next指针方向掉个头。

2. 迭代法：用三个指针"边走边翻"

2.1 核心思路

想象你在翻一排扑克牌。你手里有一张"前一张"，面前是"当前牌"，还有一张"下一张"备用。你把当前牌翻过来指向前一张，然后三张牌都往前挪一步。
三个关键指针：

• prev：已经反转好的部分的头（初始为nu