反转链表就地算法：三指针迭代与高频组合套路详解

你如果去翻各大题库，会发现反转链表的就地算法几乎是出场率最高的一题。我在刷题阶段的第一道链表题就是它，当时照着别人的代码背下来，过了几天再写，还是会把链表写断。后来自己把整个"就地"过程在纸上推了三遍，才真正理解那几行指针赋值到底在做什么。

这篇就围绕"反转链表的就地算法"展开：先讲清楚就地到底就地在哪里、为什么不能直接把数组那套反转思路搬过来；然后把迭代版三指针法完整推一遍，包括每一行代码执行后各指针的位置和含义；接着分析递归版为什么看起来优雅但藏着两个实际问题；再给出我在调试过程中总结的常见错误表和排查思路；最后说说反转链表在回文判断、区间反转、K个一组翻转里的典型套路。

适合的读者分两类：一类是刚接触链表、正在刷题的新手，这篇能帮你把指针操作的每一步都看透；另一类是已经有几个月基础、想梳理链表类题目共性的开发者，后半部分的组合套路可以直接拿去用。

1. 为什么"就地"两个字才是这道题的核心考点

在讨论代码之前，先明确一个基本问题：反转一个链表，为什么值得单独成为一道题？把链表的元素读到一个数组里反转，再新建一个链表填回去，功能上完全等价，代码写起来更直观，也不容易出错。但面试或机考里这道题的价值恰恰在于，它要求你不借助额外存储空间完成反转，也就是题目描述里常见的"在原地反转"。

链表结构本身是分散在内存里的一个个节点，彼此靠next指针串联。反转一个链表，本质上不是把数据搬来搬去，而是把所有next指针全部掉转方向。就地算法的含义是：只调整指针的连接关系，不新建任何节点、不复制数组、不开辟长度和链表规模相当的内存空间。整个反转过程只需要几个固定的辅助指针变量，空间复杂度是O(1)。

为什么考核这个点？因为在真实的工程环境里，链表往往很长。某公司的机考系统里我遇到过真实的关联数据场景，单链表有几十万甚至上百万个节点，如果每反转一次就复制一份节点数据，内存消耗是灾难性的。假设每个节点是一个复杂对象，里面带着几十个字段，反转十万个节点等于重新创建十万个对象，这中间的开销是O(n)级别的额外内存和O(n)的赋值操作。

数组反转的最优算法是双指针左右交换，这也是你在别的题目里学过的"就地"。但把双指针搬运到链表上会立刻遇到一个尴尬：链表的物理存储不连续，没有索引，你无法像数组那样同时拿到头尾两个元素，然后向中间靠拢。想要访问链表里任意一个节点，都只能从头开始顺着next指针走，单链表更是回不去前驱节点。所以链表反转需要另一套独立的思路：在遍历的过程中直接调整指针方向，而不是先定位再交换。

理解了这个背景，再看迭代法里那三个指针，就不会觉得它是一堆魔法赋值了。它做的事情本质上和数组双指针是一样的——都是O(n)时间、O(1)空间的原地整理——只是因为链表数据结构特殊，不得不用多一个临时变量来记录路径。

2. 三指针迭代法：每一步都推给你看

迭代版反转链表是所有解法的基础，后面不论是递归还是各种变形题，最终都可以回溯到这段逻辑。我把整个过程从零推导一遍。

2.1 从单链表结构说清"断链"风险

首先明确节点的定义。下面用Python写，这也是我日常刷题用的语言：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

这里要特别想清楚一个事实：当我们执行curr.next = prev这类赋值时，等于把curr指向后一个节点的唯一路径改掉了。如果这个修改发生的时候，你没有留任何变量保存原来的curr.next，那么链表在curr之后的部分就再也找不回来了。这就是常说的"断链"。

断链的可怕之处在于，它往往不会立刻报错。链表本身不会越界，程序也不会崩溃，而是会在某个你意想不到的地方安静地产生错误结果——比如遍历走到了None、陷入了循环，或者输出序列里莫名其妙丢了一截。我见过太多人在笔试题里栽在这个问题上。

就地反转的基本思路，是准备三个指针，让它们沿着链表从左往右滑动，每经过一个节点就把它与后一个节点的连接掉个方向。三个指针各司其职：prev记录已经反转完部分的头，curr记录当前要处理的节点，nxt提前保存curr原本的下一个节点。

2.2 完整代码与逐行状态追踪

就地反转的迭代写法长这样：

def reverse_list(head): prev = None curr = head while curr is not None: nxt = curr.next # 先保存当前节点的下一个节点，防止断链 curr.next = prev # 把当前节点指向前一个节点，完成反转 prev = curr # 前驱指针前进到当前节点 curr = nxt # 当前指针前进到原后继节点 return prev # 循环结束时，prev正好指向新链表的头

这段代码看起来只有四行循环体，但是每一步的指向变更都必须想清楚。我拿一个具体的链表演示：1 -> 2 -> 3 -> None。

初始化：prev是None，curr指向节点1。此时链表结构还没有任何变化，只是准备好了两个工作指针。

第一轮循环：

1. nxt = curr.next，nxt指向节点2。这一步是在"掉头"之前把退路留好。
2. curr.next = prev，节点1的next指向None。链表变成1 -> None，这一段已经完成了反转。
3. prev = curr，prev指向节点1。
4. curr = nxt，curr指向节点2。

第二轮循环前，状态是：prev是节点1，curr是节点2，nxt还是节点2（马上重新赋值）。链表大部分还保持着2 -> 3 -> None的连接，只有节点1的尾部断开了。这就是"拆一节处理一节"的过程，每次处理完一个节点，它就会脱离原来的链条，挂到新链的头部方向。

进入第二轮：

1. nxt = curr.next，nxt从节点2的next拿过来，指向节点3。
2. curr.next = prev，节点2的next指向节点1。此时链表形成3 -> 2 -> 1 -> None，但注意3的next仍然指向None，还没有参与调整。
3. prev = curr，prev指向节点2。
4. curr = nxt，curr指向节点3。

第三轮循环同样处理节点3。此后curr = nxt会让curr变成None，while循环结束，prev指向节点3。原链表的末位节点就是新链表的头，返回prev恰好得到3 -> 2 -> 1。

用一个生活化的类比帮助记忆：这就像一队人面朝右站成一列，每个人拉住前面人的衣角。你要让他们全部面朝左，但不能移动他们站的位置，只能让他们改变拉住的人。如果某个人撒手之前没看清自己原来拉的是谁，后边一串人就会散掉。prev就是已经转过来的人，curr是正在转身的人，nxt是站在curr身后还没轮到他转过身的人。

2.3 为什么循环结束条件一定是curr为空

很多初学者会把循环条件写错，最常见的是写成while prev is not None或者while nxt is not None。这两种写法最后都会导致指针越过链表末尾，在访问None的属性时报AttributeError。

判断条件用哪个指针，取决于循环体结束时谁落在链表边界之外。看上面的推导，我们每次处理完curr之后，都通过curr = nxt让curr移动到下一个待处理的节点。当链表最后一个节点处理完，nxt是None，赋值给curr之后，curr就变成了None。这个None意味着"已经没有待处理的节点了"，所以循环体应该停下来。

此时prev在哪里？在最后一个节点上，也就是新链表的头。因此循环结束后返回prev，正好就是反转链表的头部。

如果把循环条件写成while nxt is not None，第一轮循环结束后nxt指向节点1，仍然非空，循环继续，但此时curr已经被挪到了节点2，prev在节点1。第二轮nxt变为节点2，还是非空……循环会一直执行到什么时候？等循环自己把节点全部处理完，nxt会指向None，然后停下来，看起来好像也对？问题在于，当循环停下来时，prev和curr的状态已经错乱了——最典型的症状是，返回pre后，新链的头部不是null结尾，而是形成了环，打印出的链表永远走不完。

所以请你接受最早期的那个判断：内部不变式是"每轮循环开始时，curr就是当前待操作的节点"。所以curr为空就代表所有节点都操作完毕。

3. 递归反转：思路非常优雅，但别忽视两个隐藏代价

迭代版本代码已经足够简洁了，为什么还有大量解法会给出递归版本？因为在LeetCode和笔试环境里，递归解法有它的展示性价值——它把"链表反转"理解成"去掉头节点后，递归反转剩余链表，再把头节点接到尾部后面"。这个思维模型有助于理解链表的递归性质，也是后面处理更复杂问题的基础。

def reverse_list_recursive(head): # 空链表或只有一个节点时，本身就不需要反转 if head is None or head.next is None: return head new_head = reverse_list_recursive(head.next) head.next.next = head head.next = None return new_head

我还是用1 -> 2 -> 3来推演。调用reverse_list_recursive(1)，因为节点1的next不是None，所以进入递归，调用reverse_list_recursive(2)。节点2同样进入递归，调用reverse_list_recursive(3)。节点3的next是None，直接返回节点3。

回到节点2的调用层：此时new_head是节点3。执行head.next.next = head，head是节点2，head.next是节点3，这行代码让节点3指向节点2。再执行head.next = None，节点2不再指向节点3。这两步完成的效果是：3 -> 2 -> None。返回new_head仍然是节点3。

回到节点1的调用层：new_head还是节点3。head.next.next = head，此时head是节点1，head.next是节点2，节点2原本指向None，现在改成指向节点1。head.next = None，节点1的next断开。最终形态3 -> 2 -> 1 -> None，返回节点3。

逻辑上和迭代完全等价，但有一个关键差别：它从尾到头逆向处理节点，这导致了两点实际问题。

第一个问题：递归深度等于链表长度。Python默认递归深度限制在1000层左右，链表只要超过几千个节点，这段代码就直接抛RecursionError。在笔试在线评测里构造一个10万节点的链表再调用这个函数，崩溃是必然的。这不是语言问题，是递归算法的固有结构问题——每层递归都要占用调用栈空间，空间复杂度是O(n)，它本身就违背了"就地"的要求。

第二个问题：性能开销更大。每一层递归都要保存现场、压栈、返回后恢复现场，函数调用的开销远大于几行普通赋值的循环。如果你用同样的链表分别跑迭代版和递归版，在链表长度达到一定规模后，递归版的耗时差距会非常明显。我在自测里生成过10万节点的链表，迭代版本耗时大约十几毫秒，递归版本直接分钟级都算不出来，因为还没到反转就已经深度爆栈了。

那递归版是不是就不该学？也不是。在面试讲思路的时候，递归解法展示的是另一种分解问题的视角，它能帮你在解决"反转链表的一部分"这类更复杂的问题时建立直觉。实际工程和笔试里，我始终推荐迭代版本优先。能用O(1)空间解决的问题，没有理由选O(n)空间的方案。

4. 实际调试中我踩过的三个坑，以及一套通用的排查思路

反转链表代码短，但正因为短，出错后往往更让人摸不着头脑。我自己带过不少同学做这道题，发现大家的错误高度集中在这几个位置。把它们列成一张对照表，排查的时候逐项检查。

看一个具体例子。我在最初实现的时候，把循环体写成了这样：

while curr is not None: curr.next = prev prev = curr curr = curr.next

看起来很合理不是吗？问题出在curr = curr.next这一行。执行完curr.next = prev之后，curr的next已经被改成了prev，不再是原来的后继节点。于是第三步里curr其实回到了上一个节点，而不是前进一步。链表被原地转圈，程序进入了死循环。

这种"覆盖之后又读取已经改变的值"的错误，在指针操作中极其常见。面对这类问题，我的排查套路固定为三步：

第一步，画图。把链表画成方框加箭头的形式，用彩笔分别标出prev、curr、nxt三个指针的位置，手动执行一轮循环，看看两个赋值操作之后各指针是否还能维持关系。

第二步，打印指针值。写一个临时调试函数，在循环体末尾输出prev.val、curr.val、nxt.val。如果发现连续两轮的curr值没有变化或者倒退了，基本可以认定是赋值顺序或者取值来源有问题。

第三步，构造边界用例。空链表、单个节点、两个节点、三个节点这四个用例必须全部测一遍。两个节点的链表是最容易暴露返回头错误的最小例子。

这三个步骤看着基础，但真的是解决指针题效率最高的方式。我见过有人拿着一个失败的用例反复看十分钟看不出问题，一画图两分钟就定位到了。

5. 反转链表从来不会单独出现：三种高频组合套路

反转链表很少作为单独一道题出现在真实工作里。它的价值体现在被嵌入到更复杂的场景里。这里我梳理三种实际中遇到最多的组合，并分析如何用最前面的迭代逻辑去解决。

5.1 回文链表判断：快慢指针配反转

判断一条链表是否是回文，朴素思路是把值抄进数组，用双指针从两头比较，这是O(n)空间。要求O(1)空间就得靠"后半段反转"的思路：用快慢指针找到链表中点，把链表从中间拆成两段，反转后半段，再逐节点比对前半段和后半段的值。

找中点的快慢指针本身也是一个经典技巧：慢指针每次走一步，快指针每次走两步，快指针到尾时，慢指针恰好在中点附近。需要注意节点总数是奇数还是偶数时拆分的边界差异。这个组合题的复杂点不在反转逻辑上，而在拆链的边界处理。我的经验是先用两个指针找到slow的位置，把slow.next作为后半段头节点调用reverse_list函数，再把两部分逐一比较。

这里有个典型的边界细节：偶数个节点时，前半段和后半段等长；奇数个节点时，正中间的节点可以忽略不参与比较。处理方式是在拆分后半段之后，把前半段的尾部切断——否则比较时会多出中间那个节点。

5.2 反转链表指定区间：固定边界就地接缝

LeetCode第92题是"反转从left到right区间的链表"，它本质上是"整个链表反转"的一个局部版本。有了整链反转的函数，区间反转就有了两种实现路径。一种是先拆出区间内的那一段，调用reverse_list拿到反转后的区段，再把区段的前后接回去。另一种是复用三指针法，但给prev一个初始位置，而不是从None开始。

我推荐先掌握整链反转，再做区间反转。因为区间反转的整体架构拆成"找边界、反转、接缝"三个独立的步骤，每个步骤都能单独验证，出错的概率大幅降低。我见过很多同学直接在一个循环里同时维护四个指针，做得越多越容易乱。与其在循环里同时处理四个指针，不如分开做：先把区间外的前一个节点记为pre，区间内第一个记为start，区间后记为tail，然后对start开头的子链表调用reverse_list，返回新头后把pre.next指向新头，并让原区间尾部的next指向tail。

5.3 K个一组反转：循环套循环的进阶用法

按K个一组反转链表，是反转类题目里公认最难但也很典型的。它的做法是：把链表每K个节点截成一组，分别把每组反转，然后把各组首尾相接。核心逻辑可以复用reverse_list函数，只是把段的结束条件从None改成"处理了K个节点"。

我在实践中拆解这个问题的思路是：外层循环负责分段，内层循环负责把当前组内的K个节点就地反转。每组反转完之后，要记录三个位置——上一组的末尾、当前组的新头、下一组的起点——然后继续处理下一组。如果末尾剩余节点不足K个，保持原序。

这个题本质上考察的是两个能力：第一，能不能准确跨过K个节点而不越界；第二，能不能在组与组之间正确"缝合"。我建议先把前两手写熟再挑战它，如果你能不看题解自己写出来，那链表反转相关的题目基本就没有盲区了。

6. 实际工程中"就地反转"还有必要吗

前面讲的都是算法题场景，但就反转链表这个能力在工程里同样占有一席之地。在一些底层库和中间件里，链表的反转往往服务于需要逆序遍历却不想付出额外内存的场景。

我印象比较深的一次是给某个系统做数据链路重构。当时模块A把事件数据组织成一条很长的单向链，业务上要求按最新数据在前的顺序输出，也就是反转整条链。最初的实现是遍历原链，把每个节点插入到一个新链的头部，相当于生成了一个新的反转链。这个做法在数据量少的时候没有任何问题，数据规模到了几十万级别之后，每次插入都要分配新节点内存，整体耗时和内存占用都上来了。

我们用就地反转处理了原链，把整条逻辑改成"原地掉头"。数据量提升到百万级别，运行时间却比原来短了一个数量级，内存占用也基本稳定不变。这种优化不是说算法本身多神奇，而是它精确匹配了这道题背后的数据结构的真实特性。

这种经验在面试里同样可以作为加分点。当你把"就地不可以申请额外空间"从一句背诵的结论，变成你实际排查过一个线上性能问题的工具时，面试官能明显感觉到你理解的不是表面代码，而是算法的本质。我在模拟面试里听候选人讲反转链表讲过不下五十遍，能聊到"为什么需要O(1)空间再做实现优化"的，基本都会给到比较高的评价。

7. 给你一份可以直接"抄作业"的复现清单

如果你看完前面的推导想立刻把这题掌握到肌肉记忆的程度，我建议按照这样的顺序做一遍验证：

1. 找一个空白页面，画出1 -> 2 -> 3 -> 4四个节点，用笔手动模拟迭代法每一轮循环后三个指针的位置，完成后再对照我在第2节的推演。
2. 不看代码，用你熟悉的语言从零写一遍迭代版，然后把空链表、单节点、双节点、多节点四个用例都测一遍。
3. 回答自己一个问题：为什么while循环结束条件是curr为空而不是prev为空？用刚才画的图给出理由。
4. 再跑一遍递归版，在纸面上推演三个节点的递归返回过程，理解每个返回层的代码做了什么。
5. 打开你常用的在线评测系统，分别提交迭代版和递归版，观察两者在大数据量下的表现差异。
6. 做完上面几步，再尝试"反转区间"和"回文判断"两道题。如果这两道也能顺利解出来，说明反转为某类更多链表问题打下的基础已经被你真正吸收了。

说得直接一点，反转链表要学的是那根从"不会"到"会"的筋。一旦你亲手把三个指针的每一步推进和链条的变化对应起来，再看到任何指针类的题目，心里都会有一条清晰的路---定位、调整、接缝、边界验证。这种手感不是靠背代码获得的，是靠一遍一遍地画图和推导获得的。我自己当初在这道题上花的时间远超它表面上那十几行代码的规模，但事后回头看，那笔投入换来的是一整套处理指针问题的通用思维框架，直到今天都在受用。