跳至主要內容

反转链表——递归与迭代的三种写法及栈帧分析

老张2026/4/30大约 11 分钟

反转链表——递归与迭代的三种写法及栈帧分析

适读人群：Java 后端开发、准备面试的工程师 | 阅读时长：约18分钟 | 难度：Easy（但坑不少）

开篇故事

2019年，我在面试一家中厂，技术面第一题就是"反转链表"。我当时心想，这不就是送分题？三下五除二写了个迭代版，面试官看了看，问：能写递归版吗？我又写了个尾递归，面试官继续追：你知道这个递归的栈帧是怎么展开的吗？每一层递归调用返回后，指针是怎么变化的？

我懵了。

说实话，那道题我做了不下二十遍，但从来没认真想过递归的栈帧展开过程。面试官说，很多人都会背答案，但真正理解这道题的人并不多。那次面试虽然过了，但那个问题在我脑子里转了好几天。

后来我专门画了一张图，把递归展开的每一步都写清楚，才算真正搞明白了这道题。再往后带新人做题，我发现大家普遍存在一个问题：会写迭代，会写递归，但两种写法的本质差异和适用场景完全说不清楚。

这篇文章就从这里切入，把 LeetCode 206 彻底讲清楚。不只是给代码，还要讲清楚每一行代码背后发生了什么。

一、题目解析

题目：LeetCode 206. 反转链表

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]

输入：head = []
输出：[]

约束条件：

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

考点梳理：

  1. 链表指针操作的基本功——prev/curr/next 三指针协作
  2. 递归思维——把大问题拆成小问题，理解递归调用栈
  3. 空间换时间——用栈模拟递归，换一种思路理解问题
  4. 边界处理——空链表、单节点链表

这题是链表系列的基础，后面的区间反转（92题）、K组反转（25题）都是在这道题上变形。根基不牢，后面一定会翻车。

二、解法一：暴力解法——借助数组

思路

最直观的想法：先把链表里所有节点的值存进数组，然后翻转数组，最后按翻转后的顺序重新赋值给链表节点。

这个思路不需要任何链表操作的技巧，就是把问题转化成更熟悉的数组问题来解决。

缺点也很明显：额外开辟了 O(n) 的空间，而且要遍历链表两次。

完整代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 边界：空链表直接返回
        if (head == null) return null;
        
        // 第一步：收集所有节点值
        List<Integer> vals = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            vals.add(curr.val);
            curr = curr.next;
        }
        
        // 第二步：翻转列表
        Collections.reverse(vals);
        
        // 第三步：把翻转后的值重新写回链表节点
        curr = head;
        for (int val : vals) {
            curr.val = val;
            curr = curr.next;
        }
        
        return head;
    }
}

复杂度分析

  • 时间复杂度：O(n)。遍历链表一次 O(n)，翻转数组 O(n)，再次遍历 O(n)，总体 O(n)。
  • 空间复杂度：O(n)。额外开辟了一个大小为 n 的 ArrayList。

适用场景

面试中基本不会用这个，但在不熟悉链表指针操作的情况下，这个思路可以帮助快速验证逻辑。另外，在实际工程代码里，链表节点数据量不大、对内存要求不严格的情况下，代码可读性优先，写这种方式也无妨。

提交结果：击败约 15% 的用户（空间使用偏高导致排名靠后）。

三、解法二：优化解法——迭代三指针

思路

这是面试标准答案之一，也是绝大多数人第一个学会的写法。

核心思想：维护三个指针 prev、curr、next，依次把每个节点的 next 指针翻转过来。

画一个图来理解这个过程：

假设链表是 1 -> 2 -> 3 -> null

初始状态：

prev = null
curr = 1

第一次循环：

next = curr.next = 2   // 先保存 next，防止断链
curr.next = prev       // 把 1 的指针指向 null
prev = curr            // prev 前进到 1
curr = next            // curr 前进到 2

第二次循环：

next = curr.next = 3
curr.next = prev       // 把 2 的指针指向 1
prev = curr            // prev 前进到 2
curr = next            // curr 前进到 3

第三次循环：

next = curr.next = null
curr.next = prev       // 把 3 的指针指向 2
prev = curr            // prev 前进到 3
curr = next            // curr = null，循环结束

最终 prev 就是新的头节点，即 3。

关键点：一定要先保存 next，再修改 curr.next，否则会丢失后续节点的引用，发生断链。这是大家最容易忘的地方。

完整代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            // 关键：先保存 next 节点，再操作指针
            ListNode next = curr.next;
            // 翻转当前节点的指针方向
            curr.next = prev;
            // prev 和 curr 同时向前移动
            prev = curr;
            curr = next;
        }
        
        // curr == null 时，prev 正好指向原链表最后一个节点，即新的头节点
        return prev;
    }
}

复杂度分析

  • 时间复杂度：O(n)。只遍历一次链表，每个节点做常数次操作。
  • 空间复杂度：O(1)。只用了三个指针变量，不依赖 n 的大小。

适用场景

这是生产代码首选写法。逻辑清晰，没有额外空间消耗，也没有函数调用栈的风险（大链表不会栈溢出）。面试时首选这个，写完后主动提一下还有递归写法，让面试官看到你知识面的广度。

提交结果：击败约 100% 的用户（时间和空间都是最优的）。

四、解法三：最优解法——递归（附栈帧分析）

思路

递归版本代码只有几行，但理解起来需要多花一些功夫。先把代码写出来，然后专门分析栈帧展开过程。

递归的核心思想：把"反转整个链表"分解成"反转 head.next 开始的子链表，然后把 head 接到反转后链表的末尾"。

用数学归纳法来想：

  • 假设我们已经知道如何反转 n-1 个节点的链表
  • 那么反转 n 个节点的链表 = 反转后 n-1 个节点 + 把第一个节点接到最后面

递归终止条件：链表为空，或链表只有一个节点（单节点反转后是自身）。

Mermaid 图——递归调用栈展开

关键两行代码的含义：

head.next.next = head;  // 让当前 head 的后继节点，反过来指向 head
head.next = null;       // 断开 head 原来的 next 指针，防止成环

以 1 -> 2 -> 3 为例，递归到底部返回时：

第一次返回（从 reverseList(3) 返回到 reverseList(2->3)）： 此时 head = 2，head.next = 3（还没变）

  • head.next.next = head 即 3.next = 2，链表变成 2 <-> 3（双向，有环！）
  • head.next = null 即 2.next = null，环被打破，变成 3 -> 2 -> null
  • 返回 newHead = 3

第二次返回（从 reverseList(2->3) 返回到 reverseList(1->2->3)）： 此时 head = 1，head.next = 2（还没变）

  • head.next.next = head 即 2.next = 1，链表变成 1 <-> 2（有环）
  • head.next = null 即 1.next = null，环被打破，变成 3 -> 2 -> 1 -> null
  • 返回 newHead = 3

必须先设置 head.next.next = head 再设置 head.next = null，顺序不能颠倒！ 如果先执行 head.next = null，那 head.next 就变成 null 了，head.next.next 就是 null.next，直接 NPE。

完整代码

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归终止条件：空节点或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        
        // 递归反转以 head.next 为头的子链表
        // newHead 是反转后子链表的头节点，也是整个反转后链表的头节点
        ListNode newHead = reverseList(head.next);
        
        // 把 head 接到已反转子链表的末尾
        head.next.next = head;  // 让 head 的后继节点反指向 head
        head.next = null;       // 断开 head 的原始指针，防止成环
        
        return newHead;
    }
}

递归深度与栈帧分析

每次递归调用，JVM 会在调用栈上压入一个新的栈帧，保存：

  • 当前方法的局部变量（head、newHead）
  • 返回地址
  • 调用者的栈帧指针

对于长度为 n 的链表，递归深度为 n，最坏情况下栈帧消耗为 O(n)。

当 n = 5000（题目约束上限）时，每个栈帧大约几十字节，总共约 100-200KB，不会栈溢出。但如果链表长度达到几十万，就要小心了。这也是为什么生产代码倾向于用迭代版本的原因。

复杂度分析

  • 时间复杂度：O(n)。每个节点被访问恰好一次。
  • 空间复杂度：O(n)。递归调用栈深度为 n。

适用场景

递归版本代码极简，适合理解递归思维。面试中写出递归版本并能讲清楚栈帧展开，是加分项。在链表较短、对代码简洁性有要求的场景下也可以用。

提交结果：时间击败约 100% 用户，空间因为递归栈约击败 60% 用户。

五、举一反三

同类题目

LeetCode 92. 反转链表 II 反转从位置 left 到位置 right 的链表节点。是本题的区间版本，需要引入哑节点，下一篇详细讲。

LeetCode 25. K 个一组翻转链表 每 K 个节点为一组翻转，不足 K 个的保持原顺序。是本题的分组版本，难度 Hard。

LeetCode 234. 回文链表 判断链表是否回文。解法之一是反转后半段链表，然后与前半段比较，用到了本题的反转操作。

LeetCode 24. 两两交换链表中的节点 每两个节点为一组交换，是 25 题的特例（K=2）。

解题模板

链表迭代操作万能模板：

// 哑节点技巧：避免对头节点的特殊处理
ListNode dummy = new ListNode(0);
dummy.next = head;

// 三指针模板
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
    ListNode next = curr.next;  // 1. 保存 next
    curr.next = prev;           // 2. 操作指针
    prev = curr;                // 3. prev 前进
    curr = next;                // 4. curr 前进
}

递归链表操作万能模板：

public ListNode solve(ListNode head) {
    // 1. 边界条件（递归终止）
    if (head == null || head.next == null) return head;
    
    // 2. 递归处理子问题
    ListNode result = solve(head.next);
    
    // 3. 当前节点的后处理操作
    // ...
    
    return result;
}

六、踩坑实录

坑一：忘记保存 next 导致断链

这是迭代版本最经典的错误。初学者经常这样写：

// 错误写法
curr.next = prev;  // 这一行执行后，curr.next 已经被改了
prev = curr;
curr = curr.next;  // 此时 curr.next 是 prev，而不是原来的下一个节点！

正确做法是在修改 curr.next 之前，先把原来的 curr.next 保存到临时变量。

坑二：递归版本两行代码顺序搞反

// 错误写法
head.next = null;       // 先断链
head.next.next = head;  // NPE！此时 head.next 是 null

两行的顺序必须是先 head.next.next = head，再 head.next = null。很多人因为没有分析栈帧，只是死记代码，一旦紧张就写错。

坑三：递归终止条件漏掉空链表

// 不完整的终止条件
if (head.next == null) return head;  // 当 head == null 时，NPE

必须同时判断 head == null。虽然题目说输入可能是空，但在某些情况下，子问题递归到最后一个节点时，head.next == null，继续递归会传入 null，所以两个条件都要有。

坑四：以为迭代版本循环结束后 curr 是新头节点

循环结束后，curr == null，prev 才是新的头节点。我见过不少人把 return prev 写成了 return curr，返回了 null。

坑五：没有处理单节点链表的递归情况

如果只判断 head == null 而不判断 head.next == null，当输入是单节点链表时，递归会进入 head.next.next = head 这行，此时 head.next 是 null，发生 NPE。

七、总结

反转链表这道题，代码行数极少，但背后的知识点很密集：

迭代版本考的是指针操作的基本功——三个指针如何协作，操作顺序为什么不能改变；递归版本考的是对递归调用栈的理解——每一层栈帧保存了什么，返回的时候发生了什么；借助数组的暴力版本则是一种"化难为易"的思维——遇到不熟悉的数据结构，先转化成熟悉的来处理。

从这道题我学到的最重要的一点是：不要只背代码，要能在脑子里"运行"代码。面试官问你递归展开过程，不是要为难你，而是在考察你是否真正理解了。如果你能画出每一步的指针变化，那这道题的变体你基本都能搞定。

后面的 92 题（区间反转）和 25 题（K组反转）都建立在这道题的基础上，建议把这三道题连起来刷，形成知识体系。

编辑此页
最近更新:
贡献者: xiaozhangge