反转链表一部分：递归与迭代的完整拆解

1. 题目拆解与整体思路

先说清楚这是一道什么题：给定一个单链表，再给你两个位置 left 和 right，要求只把从 left 到 right 这一小段链表反转，其余部分保持原样。比如说1 -> 2 -> 3 -> 4 -> 5，left = 2，right = 4，处理完应该得到1 -> 4 -> 3 -> 2 -> 5。这类题目在算法题库里出现频率很高，也是很多面试环节用来考察链表基本功的经典题。

很多人第一眼看这个题会觉得“不就是反转链表嘛”，结果一动手就翻车。原因在于：反转整个链表是一个非常基础的操作，但反转“一部分”时，需要同时照顾区间左边的前驱节点和区间右边的后继节点。稍微有一点衔接不到位，就会出现链表成环、断链、或者返回的头节点不对这类问题。

如果你以前接触过那套在算法社区流传很广的算法框架，应该对“递归思维处理链表”这套方法论有印象。这套框架的核心观点是：不要一上来就陷入指针操作的细节，先用函数定义把问题缩小，再考虑递归出口和返回值。今天我就用 Python 把“反转链表的一部分”从递归到迭代完整拆开讲一遍，包括每一步的代码、为什么要这么写、常见的坑在哪里。

这道题我推荐两种解法：递归法和迭代法。递归法代码短、思路清晰，但空间复杂度是 O(n)；迭代法可以在 O(1) 空间内完成，实际工程中用得更多。两边的核心原理其实是互通的，所以我建议你把两种解法都看明白，而不是只背一个答案。

2. 从“反转整个链表”开始：递归框架的地基

2.1 反转整个链表的递归代码

在拆解“反转一部分”之前，必须先把最基础的反转整个链表吃透。虽然这道题最终不是直接反转整个链表，但它的核心递归逻辑完全建立在基础反转之上。

Python 代码如下：

def reverse_list(head): if head is None or head.next is None: return head last = reverse_list(head.next) head.next.next = head head.next = None return last

这段代码非常短，但信息密度很大。递归的出口是“当前节点为空，或者当前节点是最后一个节点”，这时直接返回 head。注意，当链表只有一个节点时，反转前后都是它自己，所以这个出口条件也是成立的。

递归主体里最关键的一行是head.next.next = head，很多初学者第一次看到这行代码会懵。它的意思是：让当前节点的下一个节点把它的 next 指针指回当前节点。举个例子，如果当前节点是 2，下一个节点是 3，那么执行完head.next.next = head后，链表里就出现了一个局部的反向连接：3 -> 2 -> ...。

但光有反向连接还不够，因为当前节点 head 的 next 还指向原来的下一个节点，如果不处理，链表就会出现环。所以紧接着要把head.next置为 None，把当前节点和原来的后继节点断开。

2.2 不要跳进递归，要用“函数定义”思考

很多人学递归的时候会犯一个毛病：试图在脑子里一层层展开递归过程，把每一步都模拟出来。其实链表递归题不需要这样，你只要相信函数定义，就能把问题想清楚。

reverse_list(head)的定义是：输入一个链表的头节点，返回反转后链表的头节点。那么当你调用last = reverse_list(head.next)时，你就已经把“以 head.next 开头的子链表”整个反转了，返回的 last 就是子链表反转后的新头。

现在的问题只剩下一个：如何把 head 接到这段已经反转好的子链表上？由于子链表已经反转，head.next 这个节点在反转后变成了子链表的尾巴，也就是说head.next.next就是子链表新的尾巴，它本来应该指向空节点。此时你把head.next.next = head一挂，head 就接到尾巴后面了，再把head.next置空，就完成了整条链表的反转。

用生活化的类比来解释：这就像你先让后面一整排人全部向后转，然后自己站到队尾，再把和原来邻位的联系断开。你不必关心后排人具体怎么转的，只要知道“他们完成反转后，队尾是原来紧挨着你的那个人”就足够了。

2.3 从反转整个链表到“反转前 N 个节点”

反转一部分的核心难点是：区间可能在链表中间，区间后面的节点不能丢。为此，算法框架里通常先引入一个中间问题——反转前 N 个节点。

先看代码：

successor = None def reverse_n(head, n): global successor if n == 1: successor = head.next return head last = reverse_n(head.next, n - 1) head.next.next = head head.next = successor return last

这个函数的作用是：反转链表从 head 开始的前 N 个节点，并返回反转后的新头。和reverse_list相比，变化有两个地方。

第一个变化是递归出口从“head.next is None”变成了n == 1。也就是说，递归到第 N 个节点时停下来，此时需要把这个节点的下一个节点记下来，存到successor里，因为它是区间外的第一个节点，反转完成后必须接回来，否则后半段链表就丢了。

第二个变化是最后一句从head.next = None变成了head.next = successor。原因很好理解：反转整个链表时，原链表的头节点反转后变成尾巴，它的 next 应该指向空；而反转前 N 个节点时，原链表的头节点反转后依然变成尾巴，但这个尾巴要接上原来的第 N+1 个节点，所以 next 指向successor而不是 None。

这一步是整个算法框架的核心跳跃。理解了reverse_n，再去看反转一部分，就只差最后一步转化了。

2.4 关于 Python 全局变量的小提醒

上面代码里successor用到了global声明，因为 Python 里如果在一个函数内给外部变量重新赋值，会被当成局部变量。在递归过程中，我们希望在 n == 1 时给外部的successor赋值，并且后续递归返回时能读取到这个值，所以必须声明。

如果你不喜欢全局变量，可以用一个长度为 1 的列表来包装，比如successor_box = [None]，递归里改成successor_box[0] = head.next，读取时用successor_box[0]。这种方式在很多面试场景下更干净，因为不需要在函数外维护一个全局状态。

3. 把“反转一部分”转化成“反转前 N 个节点”

3.1 核心思路：先走到 left，再套用 reverse_n

有了reverse_n这个基础函数，反转一部分就可以描述成：如果 left 等于 1，说明区间从链表头部开始，那我直接调用reverse_n(head, right)就结束了。

如果 left 大于 1，那我就把当前头节点先放下不管，递归处理head.next，同时把 left 和 right 都减 1。这个操作的物理含义非常直观：我把问题从“原点开始第 left 到第 right 个节点反转”缩小为“从第二个节点开始第 left-1 到第 right-1 个节点反转”。每递归一层，相当于把起点的指针往后移动一个节点。

来看完整代码：

def reverse_between(head, left, right): if left == 1: return reverse_n(head, right) head.next = reverse_between(head.next, left - 1, right - 1) return head

这段代码非常短，但包含了整个算法框架的精髓。递归走到 left 之前，每一层都没有对当前节点做任何修改，只是把head.next指向递归返回的结果。只有到达 left 所在的位置后，才会真正触发reverse_n的执行。

3.2 递归的返回值和状态变化详解

我们用一个具体例子推演，链表是1 -> 2 -> 3 -> 4 -> 5，left = 2，right = 4。

调用reverse_between(head_1, 2, 4)，因为 left != 1，所以执行head_1.next = reverse_between(head_2, 1, 3)。这里先不修改 head_1 的任何指针，只是等待递归返回值。

下一层调用reverse_between(head_2, 1, 3)，此时 left == 1，直接执行reverse_n(head_2, 3)。这一步会把从 2 开始的 3 个节点（也就是 2、3、4）反转，得到4 -> 3 -> 2，并且这个子链表的尾巴 2 会通过successor接到原来的节点 5 上。所以返回的头节点是 4。

回到上一层，head_1.next被赋值为 4，于是最终链表变成1 -> 4 -> 3 -> 2 -> 5。

这个例子很好地说明了：递归过程中，区间之前的节点完全没有参与反转，只是像接力棒一样把递归请求传递下去；区间内的节点通过reverse_n完成反转；区间之后的节点通过successor被无缝接回。

3.3 为什么 left 和 right 都要跟着减 1

这是初学者最容易忽略的细节。很多人会问：进入递归后，我已经往前走了一个节点，为什么 left 和 right 都要减 1，而不仅仅是 left？

原因是：reverse_between(head.next, ...)这个调用中，新的 head 是原链表的第二个节点，那么原来从全局看是“第 left 到第 right 个节点”，现在站在第二个节点的角度看，区间自然变成了“第 left-1 到第 right-1 个节点”。递归本身就是视角的不断前移，两个参数必须保持相对的区间长度不变。

如果不把 right 也减 1，那么递归到深层的reverse_n就会多反转一个节点，把区间后面的无辜节点也卷进来。我在实际写代码时曾经因为这个失误，导致区间尾部多反转了一位，输出结果看起来非常诡异，后来通过打印每一步的链表状态才定位到问题。

3.4 递归解法的空间复杂度问题

递归解法虽然代码看起来很短，但它的空间复杂度是 O(n)，因为递归调用会占用系统栈。在 Python 中，默认的递归深度限制大约是 1000 层。如果链表的长度接近或超过这个阈值，代码会直接抛出RecursionError。

所以面试时如果你选择递归解法，最好提一下这个限制，并说明工程上更推荐迭代实现。在刷题阶段，递归解法可以帮助你理解问题的结构；但在真实项目中，链表的长度不可控，迭代解法才是更稳妥的默认选择。

4. 工程上更实用的迭代解法：头插法

4.1 完整代码与逐步拆解

迭代解法是面试中最推荐的写法，它不需要额外栈空间，只需要几个指针变量就能完成。实现思路叫做“头插法”，也就是不断把区间内的节点一个个插到区间头部前面，最终实现区间反转。

先看完整代码：

def reverse_between_iterative(head, left, right): dummy = ListNode(0, head) pre = dummy for _ in range(left - 1): pre = pre.next cur = pre.next for _ in range(right - left): nxt = cur.next cur.next = nxt.next nxt.next = pre.next pre.next = nxt return dummy.next

这段代码一共只做了三件事：第一，用虚拟头节点保护整个链表；第二，把 pre 指针移动到 left 的前一个节点；第三，用头插法把 left 右侧的节点逐个搬到 pre 后面。

为了讲清楚头插法，我再用1 -> 2 -> 3 -> 4 -> 5，left = 2，right = 4 这个例子完整推演一遍。

初始状态：dummy 指向 1，pre 指向 1，cur 指向 2。第一个循环执行 left - 1 = 1 次，pre 从 dummy 变为节点 1，完全正确。

第二个循环需要执行 right - left = 2 次。

第一次循环：

• nxt = cur.next，也就是节点 3。
• cur.next = nxt.next，让节点 2 直接指向节点 4。这时链表中的 3 被“摘”出来了。
• nxt.next = pre.next，让节点 3 指向 pre 的下一个节点（当前是 2）。
• pre.next = nxt，让节点 1 指向节点 3。
• 链表状态变成1 -> 3 -> 2 -> 4 -> 5。

第二次循环：

• nxt = cur.next，注意此时 cur 还是节点 2，它的 next 是节点 4，所以 nxt 是节点 4。
• cur.next = nxt.next，让节点 2 直接指向节点 5。
• nxt.next = pre.next，让节点 4 指向 pre 的下一个节点（当前是 3）。
• pre.next = nxt，让节点 1 指向节点 4。
• 链表状态变成1 -> 4 -> 3 -> 2 -> 5。

循环结束，返回 dummy.next，也就是节点 1，整个结果和预期一致。

4.2 为什么虚拟头节点是必须的

如果没有 dummy 节点，当 left = 1 时，pre 需要指向链表的头节点之前，但链表头节点之前没有节点，你只能单独写一个 if 分支处理。用了 dummy 之后，无论 left 是多少，逻辑完全统一：pre 永远指向“区间前一个节点”，而 dummy 充当了一个假的前驱节点。

这里有一个细节值得注意：dummy 的初始值可以随便给，比如ListNode(0)，然后让它的 next 指向 head。最终返回的是dummy.next，而不是 head，因为当 left = 1 时，反转后的链表头节点已经变了，head 这个变量指向的是原链表头，不是新链表头。

我在刚学头插法时犯过一个经典错误：左端点就是 1，反转完成后直接返回 head，结果返回的是已经被移到后面的原头节点，整个输出完全错位。用了 dummy 以后，这个问题就彻底不存在了。

4.3 循环次数为什么是 right-left

很多人在写迭代法时会纠结循环次数。这里我给你一个特别容易记忆的结论：cur 永远指向区间内的第一个节点，它自己不需要移动；每次循环会把 cur 后面的一个节点搬到 pre 后面去。区间内除了 cur 以外，一共有 right-left 个节点，所以循环 right-left 次就刚好把所有节点搬到前面。

从另一个角度理解，区间长度为 right-left+1，反转后第一个节点和最后一个节点互换位置。每次头插操作会“消化”掉 cur 后面的一个节点，当所有“后面节点”都被搬到前面时，原顺序自然就反过来了。

还有一个容易踩的坑：第二步cur.next = nxt.next和第三步nxt.next = pre.next的顺序不能换。必须先把 nxt 从链表中摘除，再让 nxt 指向 pre 后面的节点，最后把 pre 指向 nxt。如果顺序错了，比如先执行nxt.next = pre.next，此时 pre.next 可能还是 cur，会导致 nxt 指向 cur，链表直接成环。

4.4 另一种迭代思路：区间内整体反转

除了头插法，还有一种迭代思路也能实现反转区间：先找到 left 的前一个节点 left_prev、left 节点、right 节点和 right 的下一个节点，然后把区间内的子链表独立反转，再接回去。

代码结构大致如下：

def reverse_between_three_pointers(head, left, right): dummy = ListNode(0, head) left_prev = dummy for _ in range(left - 1): left_prev = left_prev.next cur = left_prev.next prev = None for _ in range(right - left + 1): nxt = cur.next cur.next = prev prev = cur cur = nxt left_prev.next = prev left_node = left_prev.next # 此时需要重新获取原来的 left 节点，可以用一个变量保存 return dummy.next

这个写法的核心是：区间内的反转使用“逐节点掉头”的方式，区间外通过记录好的四个关键位置完成拼接。相较于头插法，它需要更仔细地保存原 left 节点，因为它在反转过程中被移动到了区间的尾巴处。两种迭代思路都能用，但头插法相对不容易弄丢引用，所以我个人更推荐头插法作为默认写法。

5. 常见报错与排查实录

5.1 链表成环：最常见也最隐蔽

链表成环是反转类题目里最容易犯的错误。典型表现是输出结果时程序陷入死循环，或者打印链表时出现重复的节点值。

成环的原因通常是某个节点的 next 指向了它前面的节点，形成一个闭环。比如写递归版reverse_n时，如果忘记把head.next指向 successor，而是保留原来的 next 指向，那么反转后的链表中就会有两处指向混乱。

排查成环问题有一个很实用的技巧：不要在脑海里空想，直接把链表打印出来。写一个简单的辅助函数：

def print_list(head): res = [] seen = set() while head and id(head) not in seen: seen.add(id(head)) res.append(head.val) head = head.next if head: res.append("...cycle...") print(" -> ".join(map(str, res)))

这个函数会遍历链表并把节点值记录下来，如果同一个节点被访问两次，就判定出现了环。这里用到id()是因为节点对象是唯一的，如果两个不同节点值相同但 id 不同，不会被误判。

5.2 区间端点判断错误

如果你用递归解法，最容易犯的错误是reverse_between里 left 和 right 的传入值没有同步减 1。如果只减 left 不减 right，那么递归到深处时，reverse_n的入参 n 会比预期大，导致把区间后面的节点也反转了。

如果你用迭代解法，最容易犯的是 left 和 right 从 1 开始计数还是从 0 开始计数的混淆。题目通常规定 left 从 1 开始计数，即第一个节点的位置是 1。如果写成for _ in range(left)而不是for _ in range(left - 1)，pre 就会多走一个节点，区间左边界就错了。

我建议在开始写代码前，先在注释里写清楚：dummy 指向节点 0（虚拟），pre 应该指向第 left-1 个节点，cur 指向第 left 个节点。这个注释能有效防止边界判断错误。

5.3 返回值选错

反转一部分后，链表的头节点可能是原头节点，也可能是新头节点。如果 left > 1，头节点没变，返回 head 没问题；如果 left = 1，区间包含头节点，反转后头节点变成了原来区间内的某个节点，此时返回 head 就是错的。

迭代解法统一返回dummy.next是最稳的，因为 dummy 是虚拟节点，不管 head 怎么变，dummy.next 始终指向处理完后的真实头节点。递归解法里，调用reverse_between的返回值就是新头，不要自作主张返回 head。

5.4 防御性检查与代码健壮性

刷题时题目通常会保证 left 和 right 是合法范围内，但真实业务中不一定。如果你写的代码要给别人复用，建议加上参数校验：

def reverse_between_safe(head, left, right): if head is None or left < 1 or right < left: return head length = 0 node = head while node: length += 1 node = node.next if right > length: return head # 继续正常逻辑

防御性检查本身不难，但容易在面试中加分，因为它体现了工程思维，而不只是“能把题做出来”。

5.5 常见问题速查表

6. 这套框架还能推广到哪些题目

6.1 K 个一组反转链表

K 个一组反转链表是一道比反转一部分更进阶的题目，核心思路是循环调用“反转前 K 个节点”。

你可以这么理解：先检查从当前头节点开始剩余长度是否大于等于 K，如果不满足就直接返回 head。满足的话，调用reverse_n(head, k)完成这一段的反转，拿到新头，然后递归处理剩余链表。代码框架如下：

def reverse_k_group(head, k): node = head count = 0 while node and count < k: node = node.next count += 1 if count < k: return head new_head = reverse_n(head, k) head.next = reverse_k_group(node, k) return new_head

注意这里node停在原第 K+1 个节点位置，head在经过reverse_n后变成了当前段的尾巴，它的 next 应该接上后面一段处理后的头节点。

这道题和“反转一部分”的本质完全一致：都是先处理一小段，再处理剩余部分。区别只是这里的段与段之间是连续不断的，而“一部分”只需要处理一次。

6.2 回文链表判断

判断一个链表是否为回文链表，常见做法是先找到中间节点，把后半段反转，然后逐一比较前后两段。

你不需要真的把后半段“切”出来，只需要用快慢指针找到中间节点，然后调用之前写过的reverse_list反转后半段，再从头比较。比较完以后要不要恢复原链表结构，取决于题目要求。

这里有一个值得注意的点：如果你在面试中写出这个解法，最好在口述时强调“我通过快慢指针找到中点，反转后半段，在 O(n) 时间和 O(1) 空间内完成比较”。这个思路和反转链表是同一类问题的直接延伸。

6.3 两两交换链表中的节点

两两交换相邻节点，也可以用类似框架处理。它其实是 K=2 时的 K 个一组反转，但实现上有更简洁的递归版本：

def swap_pairs(head): if head is None or head.next is None: return head nxt = head.next head.next = swap_pairs(nxt.next) nxt.next = head return nxt

这段代码和反转链表的递归结构非常像，区别在于子问题规模是每次减少 2 个节点，而且每次只反转一对而不是一整条。如果你把反转一部分的代码吃透了，再看这段代码会非常轻松。

6.4 从“背代码”到“建框架”

说了这么多扩展题目，我想强调的是：算法框架最有价值的地方并不是让你背下几个固定模板，而是训练你把那些表面上看起来不同的题目，抽象成同一组可复用的子问题。

反转一部分这道题，真正的难点只有一个：怎么把“反转区间”这个需求拆解成“先定位区间 + 执行反转 + 再拼接回去”。无论是递归版还是迭代版，本质上都没有离开这三个步骤。你把这一道题的三种解法（递归、头插、三指针）都吃透以后，再看其他链表反转类题目，基本就是在套同一种思维模式了。

7. 个人实操中的一些体会

写到这里，我再分享几点刷题和实际工程中积累的经验，算是给大家的额外提醒。

第一，链表题的调试成本比其他题型高，因为你看不到内存里的指针状态。我习惯在测试函数里写一个打印链表的辅助方法，每执行完一个关键步骤就把整个链表打出来。这个方法写起来简单，但能帮你省下大量在脑子里模拟指针操作的时间。

第二，写反转链表这类题目时，先画图，再写代码。哪怕只是简单画出 pre、cur、nxt 三个指针的位置变化，也比直接硬写强很多。我见过很多同学一上来就写代码，写完以后对指针指向的问题一脸茫然，但让他们画出每一步的链表状态，往往立刻就能找到问题所在。

第三，能写迭代就用迭代。递归的代码虽然简洁，但是在处理长链表时会遇到递归深度限制，而且面试官经常追问“能不能用 O(1) 空间实现”，迭代解法天然就满足这个要求。我个人的习惯是：先用递归理解问题结构，再用迭代实现最终方案，这样既能清晰表达思路，又能保证代码健壮性。

第四，也是最重要的一点：一定要动手把代码跑一遍，而不是只在心里过一遍。链表的指针操作非常考验精确性，错一个 next 赋值顺序，结果就完全不对。我自己每次写完反转类代码，都会在草稿纸上画一条 5 个节点的链表，手动走一遍循环过程，确认每一步的指针状态都和自己预期一致，这个方法虽然笨，但特别管用。