我一直有个习惯链表题刷完一遍会把代码删掉隔几天凭理解重新默写一遍。反转链表是练得最多的因为从“反转整个链表”到“反转前N个节点”再到“反转链表的一部分”难度是阶梯式上升的非常适合检验自己到底有没有真懂。最近又跟这道题死磕了一轮把labuladong算法框架那套递归思路配合Python重新撸了一遍发现很多之前没想透的地方这次终于通了。这篇文章就把“反转链表的一部分”完整拆开讲清楚先用递归框架一层层揭开它的本质再给迭代头插法作为工程向的解法最后附上我实际调试时踩过的坑和面试时容易被追问的边界情况。不管你是刚开始刷链表题还是已经能秒写反转整个链表但一碰到区间就发怵这篇都能帮到你。1. 题目到底在考什么先拆解需求再动手1.1 题面与第一反应题目本身不复杂给定一个单链表反转从位置 left 到位置 right 的节点最后返回反转后的链表头。限制条件通常是 1 ≤ left ≤ right ≤ 链表长度。我第一次看到这个题第一反应是迭代头插法。思路就是用一个哑节点固定在 head 前面找到 left 前一个节点作为 pre然后循环把区间内的节点一个一个往前插。这个方法很直观跑几个用例也能过但有个问题面试官只要追问一句“为什么这里要加哑节点”“循环次数为什么是 right-left 而不是 right-left1”我就有点答不利索。说白了当时只是背下了步骤没有真正理解指针之间的约束关系。后来我把思路换了个角度才发现这个题其实有三个递进的层次反转整个链表反转前 N 个节点反转区间 [m, n]这三个能力不是并列关系而是递进关系。能写反转整个链表就只差一个“后继节点要接住”的问题就能写反转前 N 个节点。能写前 N 个节点区间反转就是把它平移成一个“以某个节点为头的前 N 个节点”的问题。这就是这套递归框架最重要的启发把新问题不断归约到已经会做的问题上。1.2 为什么“归约”比“硬写”更可靠我初学链表题的时候有个坏毛病拿到题就画图画完图就撸指针。对于反转整个链表指针关系不复杂硬画没问题。一旦加了区间限制指针数量变多人脑就很难在每一轮循环里都保持清醒。经常是写着写着发现某个节点在上一轮已经被改过 next 了这一轮再改就把链表弄断了。递归框架的好处是它把复杂度藏起来了。你不需要在每一步都追踪所有指针只需要相信两件事递归函数能把子问题正确解决当前层只需要处理当前节点和子问题结果之间的关系。这种“相信”不是盲目相信而是靠边界条件来验证的。比如反转整个链表递归边界就是“只有一个节点时反转结果就是它自己”只要边界成立回溯过程中每一层做的操作又确实能保持链表完整那整个函数就是正确的。这种验证方式比盯着十几个指针来回画要可靠得多。所以我在下文会先写两个基础版本把递归的“信任链”建立起来再写区间反转。你会发现真正写到区间反转的时候核心代码只有几行剩下的都是框架。2. 地基反转整个链表与反转前N个节点2.1 反转整个链表的递归写法先说反转整个链表。这个递归版本非常经典代码短到不能再短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。递归调用reverse_list(head.next) 会返回“以 head.next 为头的那段链表反转后的新头节点”。调完递归回来当前层要做的只有两件事把 head.next 的下一个指针指向 head然后把自己的 next 置空。这里我用一个生活类比一列火车要掉头你不能整体一起调只能先让后面的车厢完成掉头再把最前面的车厢接上去。递归天然适合这种从后往前的操作。有个细节值得注意为什么最后要返回 last而不是返回别的因为反转之后原来的尾节点变成了新头节点。last 是递归最深层返回上来的它从头到尾指向的都是同一个人它才是反转后链表的入口。这个方法空间复杂度是 O(n)因为递归会压栈。面试如果要求 O(1) 额外空间那就得写迭代。但递归版的价值不在于省空间而在于它把“链表反转”这个动作抽象成了一件非常简单的事每个节点只需要改一次 next。2.2 升级反转前N个节点难点在于后继节点反转整个链表的代码很短是因为整个链表反转后不需要考虑“后面还要接谁”。但如果是反转前 N 个节点问题就变了以 head 为起点反转前 N 个节点之后第 N 个节点后面还要接上原链表的第 N1 个节点。举个例子链表是 1-2-3-4-5反转前 3 个节点结果是 3-2-1-4-5。那个 4 不能丢必须接在 1 的后面。这就需要一个变量来提前记录第 N1 个节点。我见过很多人在这一步卡住下面这段代码是用嵌套函数配合 nonlocal 实现的在 Python 里比全局变量更干净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关键点在于 n 1 时做了什么此时 head 是这一段要反转的最后一个节点把 head.next 存到 successor 里然后返回 head。后面回溯的时候每一层都会把 head.next 指向 successor这样反转后的最后一个节点就能和原链表后面的部分接上。对比反转整个链表的代码区别就两处多了 successor 记录第 N1 个节点head.next 不再直接置空而是指向 successor。为什么因为反转整个链表时head 就是全链表的最后一个节点它的 next 必须是 None。而反转前 N 个节点时head 是这一段最后一个节点但它的 next 要接后续节点不能置空。我当时第一次写这段代码漏掉了 head.next successor结果反转前 3 个节点时1 后面的链表整个丢了。后来把这个问题记下来每次写递归都先问自己这一段反转完当前节点后面要接谁3. 核心实现递归框架解决区间反转3.1 区间反转如何归约成前N问题有了 reverse_n 打底区间反转的代码竟然只剩几行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 等于 1说明从当前 head 开始就是要反转的区间起点直接调用 reverse_n(head, right) 就完事。如果 left 大于 1那就把问题往后挪一个节点区间也整体左移变成 reverse_between(head.next, left - 1, right - 1)。为什么区间参数要同时减 1因为 head 已经向后移动了一位相对于新的 head 来说区间的起点和终点都各自向前挪了一位但区间长度不变。这个“区间平移”是整个递归框架最巧妙的地方也是我第一次没有看懂的地方。我用一个具体例子跑一遍。链表是 1-2-3-4-5反转区间 [2, 4]第一层调用 reverse_between(1, 2, 4)left 不等于 1进入 else。需要先算 reverse_between(2, 1, 3)然后把结果接在 1.next 上。第二层调用 reverse_between(2, 1, 3)此时 left 正好等于 1调用 reverse_n(2, 3)也就是反转以 2 为起点、长度为 3 的链表。这一步返回的新头节点是 4。回到第一层把 head.next 指向 4也就是 1-4-...中间被反转的部分自然就是 4-3-2-5。最终得到 1-4-3-2-5。这个过程里最核心的思维转变是你不要去想“这个递归太深了我脑袋转不过来”只需要关注当前这一层。当前层只有两种可能要么我已经在区间起点直接调用 reverse_n要么我还在区间前面那我就把问题丢给下一个节点同时把区间在参数层面整体左移。另外注意一个细节reverse_between 返回的是“以传入 head 为起点的链表在区间反转后的头节点”。如果 left 1说明 head 不在区间内所以 head 本身不用动只需要把后面反转好的结果接回 head.next。如果 left 1说明 head 在区间内head 会被 reverse_n 挪到区间的尾部不能再返回 head 作为新头节点所以要直接返回 reverse_n 的结果。3.2 完整可运行代码我把完整代码贴在这里包含链表构造和打印函数你可以直接跑起来验证class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_linked_list(values): dummy ListNode() cur dummy for v in values: cur.next ListNode(v) cur cur.next return dummy.next def print_linked_list(head): values [] while head: values.append(str(head.val)) head head.next print( - .join(values)) 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 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 if __name__ __main__: head build_linked_list([1, 2, 3, 4, 5]) print(原始链表) print_linked_list(head) result reverse_between(head, 2, 4) print(反转区间 [2, 4]) print_linked_list(result)这个版本用了 global successor是为了跟原始框架保持一致便于理解。实际工程里我更推荐用嵌套函数加 nonlocal避免全局变量在多次调用之间互相污染def reverse_between(head, left, right): successor None def reverse_n(node, k): nonlocal successor if k 1: successor node.next return node last reverse_n(node.next, k - 1) node.next.next node node.next successor return last if left 1: return reverse_n(head, right) head.next reverse_between(head.next, left - 1, right - 1) return head两种写法运行结果完全一样但后者把 successor 的作用域限制在 reverse_between 内部不会影响外部环境。4. 另一条常用路线迭代头插法4.1 哑节点与双指针的实际操作递归框架虽然优雅但并不是所有人都习惯。如果你在面试中明确要求 O(1) 空间复杂度就得用迭代。迭代头插法同样不难代码我直接给出来def reverse_between_iter(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第一步是创建哑节点 dummy它指向 head。为什么要这个哑节点因为如果 left 恰好等于 1反转后头节点会变涉及头节点的操作就要单独写分支。有了 dummypre 从 dummy 开始就能统一处理 left1 和 left1 两种情况代码可以少写一个 if。第二步让 pre 走到 left 的前一个节点。这里循环 left-1 次因为 dummy 本身占用了一个位置。之后 cur 指向 pre.next也就是区间第一个节点。第三步执行 right-left 轮移动。每一轮做的事情非常有规律取出 cur 后面的节点 nxt先让 cur 直接跨过 nxt 指向 nxt 的下一个节点再把 nxt 插到 pre 的后面。这样每一轮区间内的一个节点就被“顶”到最前面反复执行之后整个区间就地反转。我用 1-2-3-4-5反转 [2, 4] 来演示初始pre 1cur 2。第一轮nxt 3。操作后链表变成 1-3-2-4-5。注意 cur 仍然是 2但 cur.next 已经变成 4。第二轮nxt 4。操作后链表变成 1-4-3-2-5。此时 cur 还是 2cur.next 变成 5区间 [2, 4] 已经反转为 4-3-2。这个过程中cur 始终没有移动它一直指向区间内最后一个节点而 pre 也始终固定在区间前一个位置。每次把 nxt 插到 pre 后面就像一个“冒泡”的过程把后面的节点不断提到最前面。4.2 递归与迭代怎么选很多读者会纠结到底该记哪种写法。我的建议是两种都要会但理解层次不同。对比维度递归框架迭代头插法核心思想归约把区间问题转成前N问题指针操作逐轮头插代码量少核心约10行略多但也不复杂空间复杂度O(n)递归栈O(1)理解门槛较高需要理解递归回溯较低适合画图推演边界处理靠 left 1 分支靠 dummy 统一处理面试展示效果体现框架思维和抽象能力体现对指针细节的控制力我个人的实际经验是面试中优先写递归框架。原因很实在递归代码更短逻辑更接近“思路本身”写着写着不容易在细节上出错。面试官如果追问空间复杂度你再补一句“递归会占 O(n) 栈空间如果需要 O(1) 空间我可以改成迭代写法”然后现场切换过去这反而成了加分项。但有一些场景是必须用迭代的链表非常长比如有几万个节点递归会直接栈溢出。这时候用迭代头插法最稳妥。工程上我基本只用迭代递归更多用来分析和教学。5. 边界条件与高频踩坑记录5.1 面试官最爱问的边界情况链表题能不能拿全分很大程度上看边界条件处理得干不干净。这几种情况我在面试和帮别人 review 代码时反复见过left 等于 1也就是从第一个节点开始反转。递归法会走 left 1 分支迭代法靠 dummy 节点统一处理。这个分支如果在迭代法里漏掉就会在反转后返回错的头节点。left 等于 right区间只有一个节点链表应该原封不动。递归法会调用 reverse_n(head, 1)此时只记录 successor 并返回 head等于什么都没做。迭代法的内层循环执行 0 次链表不变。这个用例用来验证代码是否对“退化区间”免疫。right 等于链表长度说明区间一直到链表末尾。这时候 reverse_n 里的 successor 记录的是 None反转后末尾节点指向 None也是正确的。迭代法里 cur.next nxt.next 这一步nxt.next 可能是 None赋值不会出错。链表只有一个节点且 leftright1。递归边界和迭代循环都能正确处理。空链表。直接返回空即可一般题目不会给空链表但健壮性检查最好还是写上。这些边界不是考官故意刁难而是用来判断你到底理解不了解题思路。你能主动把这些用例说出来会比闷头写完再等考官发问要加分。5.2 我实际调试中遇到的那些坑第一个坑递归里忘了把调用结果接回 head.next。reverse_between 中当 left 1 时如果只写 reverse_between(head.next, left-1, right-1) 而不把返回值赋给 head.next那反转好的子链表就丢了原链表会从 head 后面断掉。这个赋值不是可选的它是连接原链表和子链表的关键。第二个坑迭代法里改指针的顺序搞反。我一开始写头插法时先执行 pre.next nxt再执行 cur.next nxt.next结果直接把链表断成两截。因为 pre.next 被改动后nxt 已经独立出来再想通过 nxt.next 找后面的节点就找不到了。正确顺序永远是先保存 nxt 的下一个节点再改 cur.next最后改 pre.next。你可以理解成先拿住绳子的一头再剪开中间。第三个坑successor 在多次调用之间残留。如果你用全局变量 successor跑完一个测试用例之后它里面还留着上一个链表的信息。下一次调用 reverse_n 时如果链表长度不同或者区间不同可能读到旧的 successor 值。我自己的解决办法是用嵌套函数加 nonlocal把作用域收窄或者在每个测试用例重新初始化 successor。第四个坑递归深度过大导致栈溢出。这个坑一般在刷题时遇不到题目给的链表长度很小。但如果你拿这个递归实现去处理生产环境里的大链表就等着爆栈。我的原则是递归思路用来分析问题工程代码一律迭代。还有一个细节很多人会忽略reverse_n 的参数 n 是“从当前节点开始往后数 n 个节点”它和链表的总长度无关。理解这一点才能理解为什么要让 reverse_between 递归时把 right 也同步减 1。这就好比你在看一把尺子从某个刻度开始量长度起点不断右移终点刻度也要跟着右移量出来的长度才不会变。刷链表题这么多年我最大的体会是链表操作题表面上考指针实际上考的是你有没有“把问题变小”的意识。labuladong这套递归框架对我启发最大的地方就是把一个区间反转问题拆成了“前N个节点反转”这个更小的子问题再通过递归一层层把起点推到区间首位。整个过程不需要把每个指针都盯死反而比硬写指针更不容易出错。如果你正在刷题我强烈建议你亲手把这个框架走一遍先默写反转整个链表再写反转前 N 个节点最后写区间反转。你会发现三次递进下来你对递归的理解会有一个质的飞跃。最后再分享一个小技巧写完递归代码后把函数调用栈画在草稿纸上只画三层就能看出 80% 的 bug 在哪里。这个习惯比刷十道题都有用。