反转链表：3步走通2种实现，迭代与递归一篇讲透

反转链表：3步走通2种实现，迭代与递归一篇讲透

【免费下载链接】algorithm-base一位酷爱做饭的程序员，立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base

反转链表（Reverse Linked List）是刷链表题绕不开的第一道关，思路一听就懂，但自己一写就总在手忙脚乱中把链弄丢。本文基于 algorithm-base 项目的链表篇教程，带你先建立"指针逐个掉头"的心智模型，再分别拆解迭代和递归两种实现，最后给出选型建议和练习路线，帮你把这道题真正变成基本功。

30秒直觉

用一句话建立心智模型：反转链表就是从头走到尾，边走边把每个节点的箭头拧到身后，走完时最后一个节点自然成了新头。

反转前：1 -> 2 -> 3 -> None 反转后：None <- 1 <- 2 <- 3 （3 成为新头）

注意一个前提：题目只允许修改节点的指向，不允许改节点的值。所以"倒着取节点拼一条新链"这类思路是走不通的，我们只能动箭头。

方法A：三指针迭代，从前往后逐个掉头

先看懂掉头这个动作

大白话：每个节点原本指向"下一个人"，反转就是让它改口指向"上一个人"。做这件事只需要三个角色——

• prev：已反转部分的头（起点时是 None，即新链表的"尾巴"）
• cur：当前正要掉头的节点
• nxt：临时记住cur的下一个，防止掉头后找不到路

三个指针如何一步步推进

以1 -> 2 -> 3为例，跟着走三轮（👇 看prev | cur的分隔线在哪）：

初始： None | 1 -> 2 -> 3 -> None prev cur 第1轮后（1 掉头指向 None）： None | 1 | 2 -> 3 -> None prev cur 1.next = None 第2轮后（2 掉头指向 1）： None <- 1 | 2 | 3 -> None prev cur 第3轮后（3 掉头指向 2）： None <- 1 <- 2 | 3 prev cur cur 走完变 None，prev 停在 3，它就是新头。

整个过程prev永远走在"已处理"的一侧，cur永远走在"待处理"的一侧，两者的分界线每次后移一格，这就是迭代反转的全部节奏。

逐轮该做哪四件事

每轮固定四步，顺序不能乱：

1. nxt = cur.next：先记住下一个节点（这一步不做，链表当场断掉）
2. cur.next = prev：当前节点掉头，指向已反转部分
3. prev = cur：分界线右移，当前节点并入已反转部分
4. cur = nxt：进入下一轮

Python 实现

class Solution: def reverseList(self, head: ListNode) -> ListNode: prev = None # 已反转部分的头，初始为空 cur = head # 待反转部分的头 while cur: nxt = cur.next # 1. 先存下一个，防止断链 cur.next = prev # 2. 当前节点掉头 prev = cur # 3. 分界线右移 cur = nxt # 4. 处理下一个节点 return prev # cur 走完，prev 即新头

空链表和单节点不需要特判：循环要么不执行（返回 None），要么走一轮就结束（返回唯一节点），天然覆盖了边界。

方法B：递归，从尾部开始才顺

为什么先去尾巴

换个角度看这道题：如果让你从后往前处理，反转反而很自然——最后一个节点不用动（它就是新头），倒数第二个指向它……难点在于单链表只能从前往后走，而递归恰好能帮你"先冲到尾巴"。这就是递归写法的切入点：把"掉头"推迟到回来的路上做。

返回路上如何完成翻转

还是以1 -> 2 -> 3为例：

下行（递）：f(1) -> f(2) -> f(3) 3 是最后一个节点，命中基准条件，直接返回 3 上行（归）： 回到 f(2)：3.next = 2，然后 2.next = None 得到 3 -> 2 回到 f(1)：2.next = 1，然后 1.next = None 得到 3 -> 2 -> 1

关键两行head.next.next = head（让下一个节点回指自己）和head.next = None（切断旧方向，防止两个节点互相指成环），就是上行时每个节点要做的全部事情。

逐行该做哪三件事

1. 命中基准条件：head为 None 或只剩一个节点，它自己就是（子链的）新头，原样返回
2. new_head = self.reverseList(head.next)：把剩下的事交给尾部，拿到反转后子链的新头
3. head.next.next = head且head.next = None：把当前节点挂到子链前面，并断开旧方向
4. return new_head：每一层都返回同一个"最终新头"，保证最外层拿到的也是它

Python 实现

class Solution: def reverseList(self, head: ListNode) -> ListNode: # 基准：空链或最后一节点，自己就是新头 if head is None or head.next is None: return head new_head = self.reverseList(head.next) # 先反转尾部 head.next.next = head # 让下一个节点回指自己 head.next = None # 切断旧方向，防环 return new_head

迭代和递归的行数差不多，但递归把"记下一个节点、移动两个指针"压缩成了一次调用和两行赋值，读起来更紧凑。

两种实现怎么选

选型建议：

• 默认写迭代。空间 O(1)、不怕长链，机试和日常题里它最省心。
• 递归适合两个场合：面试官明确想听递归思路时；以及后面要写 K 个一组反转（LeetCode 25）这类题时，按组切分 + 递归下探的结构会比迭代好写很多。

延伸：两个常见的变形入口

只反转一段（LeetCode 92 反转链表 II）。入口是"定位 + 局部反转 + 重新接回"：先走到第left个节点前，把left..right这段用上面的三指针法原样反转，最后把断开的两头接回去。难点不在反转本身，而在两头重接时别丢指针。项目里有对应的分步解析：animation-simulation/链表篇/leetcode92反转链表2.md。

K 个一组反转（LeetCode 25）。思路是把链表看成若干"块"，每块凑够 K 个就整块反转，凑不够保持原样。单块反转直接复用三指针法，块与块之间递归处理。掌握 206 之后这道题的增量部分只是分组和拼接。

动手练习路线

1. 先闭卷手写迭代版，哪怕花二十分钟，重点确认那四步的顺序能自己默出来
2. 对照动画自查：打开项目里的 完整动画教程，逐轮核对每轮结束后prev和cur的位置是否和你手写时推演的一致
3. 提交验证边界：空链表、单节点、两节点三种输入各跑一遍，再提交 LeetCode
4. 顺带把递归版默写一遍，卡壳就回看"下行不动、上行才反转"那节；更多链表题可以逛 animation-simulation/链表篇/

反转链表这道题没有捷径，就是把"存下一个、掉头、移分界"这个循环在脑子里过成肌肉记忆。接下来建议直接上手 LeetCode 92，把局部反转的拼接练熟，K 个一组反转水到渠成。

【免费下载链接】algorithm-base一位酷爱做饭的程序员，立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base