1. 为什么链表反转是面试官的“心头好”？

如果你正在准备技术面试，尤其是那些一线大厂的面试，我敢打赌，你几乎百分之百会遇到链表相关的问题。而在所有链表问题里，“反转链表”就像是一道“招牌菜”，出场率高得惊人。我当年面试的时候，几乎每场必考，后来自己做了面试官，也总爱拿这道题开场。为什么？因为它太“完美”了。

你想啊，一道好的面试题，不能太简单，也不能太难到让人无从下手。它得像一把尺子，能量出候选人的基本功扎不扎实，思路清不清晰，代码写得规不规范。反转链表这道题，恰好就卡在这个黄金点上。它代码量不大，但里面包含了指针操作、迭代思维、递归理解，甚至还能考察你对边界条件的处理（比如空链表、单节点链表）。面试官让你写，三五分钟就能看出你的代码功底。更“狠”一点，他会接着问：“你能用几种方法实现？” 这时候，如果你只会一种，可能就有点悬了；如果你能流畅地说出两三种，并且能画出图来解释，那印象分绝对蹭蹭往上涨。

所以，别把它当成一道简单的算法题。它是你展示自己思维严密性和编码能力的舞台。今天，我就把我这十年来见过的、用过的、考过别人的三种最核心的反转链表方法，掰开了、揉碎了讲给你听。我保证，就算你之前对指针绕得头晕，看完这篇，也能彻底搞明白，下次面试遇到，能稳稳地拿下。

2. 头插法：最符合直觉的“搬家”策略

当我第一次被问到怎么反转链表时，脑子里蹦出来的第一个想法就是：再造一条新链子！这就像你有了一串用绳子穿起来的珠子（旧链表），现在想把它倒过来。最笨但最稳的办法是什么？就是准备一条新绳子（新链表头），然后从旧绳子上把珠子一颗一颗拆下来，每次都插到新绳子的最开头。这就是头插法，它特别直观，非常适合新手理解和记忆。

2.1 图解“搬家”全过程

我们假设有一条链表：1 -> 2 -> 3 -> 4 -> 5 -> NULL。我们的目标是变成 5 -> 4 -> 3 -> 2 -> 1 -> NULL。

首先，我们得准备一条“新绳子”，也就是一个新链表的头指针。一开始，这条新绳子是空的，我们叫它 newHead，并且让它等于 NULL。同时，我们需要一个“搬运工”指针 cur，它从旧链表的头节点 1 开始。

第一步：拆下第一颗珠子（节点1）

1. 为了防止旧链表丢掉后面的珠子，我们得先让一个“保安”指针 nextNode 记住 cur 的下一个节点，也就是节点 2。nextNode = cur->next。
2. 然后，把节点 1 从旧链上“拆”下来，让它指向新链表的当前头（目前是 NULL）。执行 cur->next = newHead。现在节点 1 自己成了孤零零的一个节点，指向 NULL。
3. 接着，把新链表的头 newHead 更新为这个刚拆下来的节点 1。newHead = cur。
4. 最后，让搬运工 cur 去处理下一颗珠子，也就是保安记住的那个节点 2。cur = nextNode。

此时状态：旧链表剩下 2->3->4->5->NULL，新链表是 1->NULL。

第二步：拆下第二颗珠子（节点2） 过程一模一样：

1. nextNode 记住 cur（节点2）的下一个节点 3。
2. 让节点 2 的 next 指向当前的新链表头 newHead（也就是节点1）。于是形成了 2->1 的连接。
3. 更新 newHead 为节点 2。
4. cur 移动到节点 3。

此时状态：旧链表剩下 3->4->5->NULL，新链表是 2->1->NULL。看，反转的效果已经开始出现了！

重复这个过程，直到搬运工 cur 为空，说明旧链表上的珠子全搬完了。此时 newHead 指向的就是新链表的头，也就是原链表的最后一个节点 5。整个链表反转完成。

2.2 代码实现与逐行解析

下面我们用 C++ 来实现这个逻辑。我会在每一行关键代码后面加上注释，让你看清楚每一步在干什么。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    // 初始化新链表的头为空
    ListNode* newHead = nullptr;
    // 搬运工指针，从旧链表头开始
    ListNode* cur = head;

    // 只要旧链表上还有节点没搬完，就继续
    while (cur != nullptr) {
        // 【保安行动】先保护现场：记住当前节点的下一个节点，防止丢失
        ListNode* nextNode = cur->next;

        // 【核心操作：头插】将当前节点插入新链表头部
        // 让当前节点指向新链表现在的头
        cur->next = newHead;
        // 更新新链表的头为当前节点
        newHead = cur;

        // 【搬运工移位】处理下一个节点
        cur = nextNode;
    }

    // 循环结束，返回新链表的头
    return newHead;
}

几个容易踩的坑：

1. 忘记保存 nextNode：这是最经典的错误。如果你在改变 cur->next 之前，没先用一个变量把原来的 cur->next 存起来，那么整个旧链表从 cur 之后的部分就彻底丢失了，程序会崩溃。
2. 循环条件判断：一定是 while (cur != nullptr)，而不是 while (cur->next != nullptr)。后者会导致最后一个节点没有被处理，无法搬到新链表。
3. 返回值：最后返回的是 newHead，不是 cur。循环结束时 cur 肯定是 nullptr。

头插法好理解，空间复杂度是 O(1)（只用了几个指针变量），时间复杂度是 O(n)（遍历一遍链表）。但它创建了一个逻辑上的“新”链表。接下来我们看一种更“原地”的方法。

3. 迭代法（三指针法）：原地翻转的“太极推手”

如果说头插法是“另起炉灶”，那么迭代法就是“就地改造”。它不需要一个新链表的头，而是直接在原来的链表上，通过调整节点之间指针的指向来完成反转。因为通常需要用到三个指针来协同工作，所以也叫“三指针法”。这个过程有点像太极推手，通过巧妙的劲力转换，让链表的“势”从头到尾倒转过来。

3.1 图解指针的“乾坤大挪移”

我们还是用链表 1 -> 2 -> 3 -> 4 -> 5 -> NULL 来演示。

我们需要三个指针：

• prev：指向当前节点 cur 的前一个节点。可以理解为“已经反转好的部分的头”。初始时，prev 是 NULL，因为第一个节点反转后前面应该没有节点。
• cur：当前需要处理的节点。初始时，cur 是原链表的头 head。
• nextNode：指向当前节点 cur 的下一个节点。它的作用和头插法里的“保安”一样，是为了防止丢失后续链表。

第一步：初始化与第一次翻转

1. prev = NULL, cur = 节点1, nextNode = cur->next (即节点2)。
2. 进行核心操作：让 cur 的 next 指针掉头，指向 prev。执行 cur->next = prev。于是，节点1 -> NULL。现在节点1成了反转后部分的尾巴（目前也是头）。
3. 指针整体前移：prev 移动到 cur 的位置（prev = 节点1），cur 移动到 nextNode 的位置（cur = 节点2）。为处理下一个节点做准备。

此时状态：prev 指向 节点1（它是已反转部分的头），cur 指向 节点2，原链表从节点2开始的部分 2->3->4->5 还未处理。

第二步：处理第二个节点

1. 更新 nextNode = cur->next (即节点3)。
2. 再次翻转：cur->next = prev，即让 节点2 -> 节点1。
3. 指针前移：prev = 节点2, cur = 节点3。

此时状态：已反转部分为 2->1->NULL，prev 指向其头节点2，cur 指向待处理节点3。

不断重复这个过程，你会发现 prev 始终指向已经反转好的那部分链表的头，cur 指向即将要处理的节点。就像有一道分界线，prev 在后面（已反转），cur 在前面（未反转），每次操作都把 cur 拉过来接到 prev 的前面，然后大家一起向前走一步。

最终状态：当 cur 走到原链表末尾的 NULL 时，循环结束。此时，prev 正好指向原链表的最后一个节点 5，而整个链表已经被完美地反转了，5->4->3->2->1->NULL。所以函数返回 prev。

3.2 代码实现与关键点

ListNode* reverseList(ListNode* head) {
    // 初始化三个指针
    ListNode* prev = nullptr; // 已反转部分的头，初始为空
    ListNode* cur = head;    // 当前待处理节点
    // 注意：nextNode 在循环内部定义，因为每次都需要 cur 的下一个

    while (cur != nullptr) {
        // 1. 保安行动：保存下一个节点
        ListNode* nextNode = cur->next;

        // 2. 核心翻转：当前节点指向前一个节点
        cur->next = prev;

        // 3. 指针整体前移：为下一次迭代做准备
        prev = cur; // 已反转部分的头更新为当前节点
        cur = nextNode; // 当前节点移到下一个待处理节点
    }

    // 循环结束时，cur为NULL，prev是新的头节点
    return prev;
}

迭代法的精妙之处：

1. 原地操作：没有占用额外的链表空间，只是通过改变指针指向来完成，空间效率极高。
2. 逻辑清晰：三个指针各司其职，prev 记录成果，cur 进行加工，nextNode 保驾护航。循环体四行代码（保存、反转、移动prev、移动cur）是固定套路，非常容易记。
3. 边界处理自然：对于空链表（head == nullptr），循环直接跳过，返回的 prev 初始值 nullptr 也是正确的。

这是面试中最受青睐的写法，因为它简洁、高效，而且能很好地体现你对指针操作的理解。务必做到能徒手白板写出这段代码。

4. 递归法：一种优雅但需要小心的“后发制人”

递归法理解起来稍微有点绕，但代码写出来非常简洁优雅，能体现你的编程功底。它的核心思想是：“我不管前面怎么乱，我只负责把我这个节点和后面已经反转好的链表处理好”。这是一种“自顶向下”再“自底向上”的思考方式。

4.1 理解递归的“套娃”与“回溯”

我们不再从第一个节点开始思考，而是想象一下，如果链表的后 n-1 个节点已经神奇地被反转好了，那么我需要做什么才能让整个 n 个节点都反转？

假设链表是 1 -> 2 -> 3 -> ... -> n -> NULL。 假设从节点 2 开始的子链表 2->3->...->n 已经被递归函数反转成了 n->...->3->2->NULL。我们称这个反转后的子链表头为 reversedSubListHead。

现在的情况是：

• 节点 1 仍然指向节点 2。
• 而 reversedSubListHead 指向 n，n 最终指向 NULL。

为了让节点 1 也加入这个反转序列，我们需要做两件事：

1. 让节点 2（现在是反转子链表的最后一个节点）的 next 指向节点 1。即 2->next = 1。
2. 让节点 1 的 next 指向 NULL，成为新的尾巴。

但这里有个问题，在只给定子链表头 reversedSubListHead 的情况下，我们很难直接找到节点 2（即原来的头，现在的尾）。不过，我们有一个更巧妙的办法：在递归“递”下去的过程中，我们并没有切断节点 1 和节点 2 的联系。

所以，更标准的递归思路是：

1. 递归反转以 head->next 为头的子链表。这个递归调用会返回反转后的子链表的头，我们记作 newHead。
2. 在递归“归”回来的过程中，我们处于这样一个状态：newHead 指向子链表的头（原链表的尾），而 head 仍然指向子链表反转前的头（即 newHead 现在的尾）。那么，我们只需要让 head->next（也就是子链表的旧头/新尾）的 next 指向 head 自己，再把 head->next 置为 NULL 即可。

听起来还是有点抽象？我们来看代码和分解步骤。

4.2 代码实现与递归深度剖析

ListNode* reverseList(ListNode* head) {
    // 递归终止条件：链表为空或只有一个节点，无需反转，直接返回
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    // 递归调用：反转以第二个节点开始的子链表
    // 假设这个调用能正确返回反转后的子链表头，我们叫它 newHead
    ListNode* newHead = reverseList(head->next);

    // 递归“归来”后，开始处理当前节点 head
    // 此时：head 指向 1, head->next 指向 2（但子链表 2->3->4->5 已经反转为 5->4->3->2）
    // 我们需要让 2 的 next 指向 1，即让新链表的尾巴连接上当前节点
    head->next->next = head;
    // 断开当前节点原来的指向，让它成为新的尾巴
    head->next = nullptr;

    // 返回新的头节点，这个头节点来自最深层的递归调用（原链表的尾节点）
    return newHead;
}

让我们一步步拆解链表 1->2->3->NULL：

1. 首次调用 reverseList(1)。head 是节点1，不满足终止条件。进入递归：newHead = reverseList(2)。
2. 第二次调用 reverseList(2)。head 是节点2，不满足终止条件。进入递归：newHead = reverseList(3)。
3. 第三次调用 reverseList(3)。head 是节点3，它的 next 是 NULL，满足终止条件，直接返回节点3。所以对于 reverseList(2) 来说，newHead 得到了节点3。
4. 回到 reverseList(2) 的上下文：
   • head 是节点2。
   • newHead 是节点3（此时子链表 3->NULL 反转后就是 3->NULL，头是3）。
   • 执行 head->next->next = head，即 2->next 是节点3，让 3->next = 2。于是链表变为 3->2。
   • 执行 head->next = nullptr，即 2->next = NULL。链表现在是 3->2->NULL。
   • 返回 newHead，即节点3。
5. 回到 reverseList(1) 的上下文：
   • head 是节点1。
   • newHead 是节点3（从上层递归返回的）。
   • 执行 head->next->next = head，即 1->next 是节点2，让 2->next = 1。于是链表变为 3->2->1。
   • 执行 head->next = nullptr，即 1->next = NULL。链表现在是 3->2->1->NULL。
   • 返回 newHead，即节点3。

最终，我们得到了反转后的链表 3->2->1->NULL，头节点是3。

递归法的注意事项：

1. 栈溢出风险：递归需要函数调用栈。如果链表非常长（比如几万、几十万个节点），递归深度过深可能导致栈溢出错误。这是递归法最大的缺点，在实际工程中需要谨慎使用。
2. 理解难度：递归代码虽短，但理解其运行过程需要一定的抽象思维。务必画图或使用调试器跟踪，理解“递”和“归”两个阶段。
3. 简洁优雅：一旦理解，你会被这种数学归纳法式的简洁美所吸引。它在面试中能为你加分，但最好同时能说出迭代法作为更优的实践方案。

5. 三种方法对比与实战选择

讲完了三种方法，我们来做个全面的对比，让你知道在什么场景下该用哪一种。

特性	头插法	迭代法（三指针）	递归法
核心思想	创建新链表，不断将旧链节点插入新链头部。	原地操作，使用三个指针逐个翻转节点指向。	将问题分解为：先反转子链表，再处理当前节点。
空间复杂度	O(1)	O(1)	O(n) （函数调用栈空间）
时间复杂度	O(n)	O(n)	O(n)
优点	直观，容易理解和实现，不修改原链表头指针。	最常用、最推荐。原地修改，空间效率最高，逻辑清晰。	代码极其简洁，体现递归思维和编程功底。
缺点	逻辑上创建了新链表（虽然节点是旧的）。	需要小心处理指针移动顺序。	链表过长时栈溢出风险，理解成本较高，调试困难。
面试推荐度	★★★☆☆ （可作为第一种思路）	★★★★★ （必须掌握，最佳答案）	★★★★☆ （可作为扩展，展示知识广度）

给新手的实战建议：

1. 首选迭代法：无论是面试还是实际项目，迭代法都是首选。它没有递归的栈溢出风险，空间效率最优，代码也足够简洁明了。务必做到闭着眼睛都能写出来。
2. 理解头插法：头插法是理解链表操作的一个很好起点。当你对指针操作还不熟练时，先从它开始画图，能帮你建立信心。
3. 掌握递归法：递归法要能解释清楚。面试时，你可以先说：“我可以用迭代和递归两种方法实现。迭代法是更优解，但递归法思路很有趣，我给您写一下。” 这样既展示了最优方案，又体现了你的知识储备。
4. 一定要画图！我见过太多人觉得自己懂了，一写就错。动手在纸上画一下节点和指针的变化过程，是理解链表问题最有效、没有之一的方法。面试时，边画图边讲解，能让面试官清晰地跟上你的思路。

链表反转的变体问题很多，比如“反转链表的一部分”、“每k个节点一组进行反转”等等，但它们的内核都是我们今天讲的这三种技巧。把这基础打牢了，再遇到那些变体，你无非就是多考虑一下边界和区间，核心的翻转操作代码块都是现成的。下次面试再遇到这道题，希望你能自信地告诉面试官：“我有三种写法，您想先看哪一种？”