很多人在写链表反转时容易卡住不是没记住代码而是没想明白那三根指针到底在干什么。你是第一次接触这道题也好还是刷过几轮又忘了也罢只要把“就地”两个字理解透把指针的每一步在纸上画一遍这个经典操作基本就彻底拿下了。本文从问题本质开始讲全程走一遍迭代三指针法、递归法和头插法再补上我这些年调试链表时踩过的各种坑最后的变体题部分也建议认真过一遍因为反向链表就是你后面做区间反转、K个一组反转一类题目的基本功。1. 先搞清楚什么才算“就地”反转链表1.1 链表结构决定了算法必须跑在指针上链表和数组最大的区别在于存储方式。数组在内存里是一段连续的空间所以按下标访问是O(1)的链表则是一堆零散节点每个节点里除了存数据还要额外存一个指向下一个节点的指针。这让链表的访问只能从头节点开始一个节点一个节点地沿着next指针往下走。也就是说链表天然不具备随机访问能力。反转链表要做的事情很直观原本从头向尾的指针方向全部掉转成从尾向头。对每个节点来说它的next指针不再指向原来的后继而是指向前驱。最终结果就是原来的尾节点变成新的头节点原来的头节点变成新的尾节点。有同学说把链表读进数组反转数组再重新串成链表行不行。行功能上是能实现的但那占用了O(n)的额外空间完全没有必要的开销。所以面试和工程里要求的一般都是就地算法也就是在原链表上直接进行调整空间复杂度是O(1)。1.2 “就地”到底在约束什么就地in-place意味着你不能依赖数组、栈这样的额外数据结构去暂存所有节点。整个过程中能额外创建的最多就是几个指针变量。几个指针变量是常数级开销不随链表长度变化这才叫作O(1)空间复杂度。这其实很像整理一串环扣在一起的链条。你需要把每一个环的开口方向都拧到反方向并且只能在你手上完成不能把整串链条拆下来放在桌面上再重新拼装。你每次只需要记住“上一个环”“当前环”“下一个环”这三个状态就能沿着链条一路拧下去。这就是迭代三指针法的物理直觉。之所以强调这个是因为很多人一上来就写递归。严格来说递归版本的核心逻辑也是O(1)的“额外指针”但因为递归调用要占用函数调用栈空间复杂度是O(n)的。所以如果题目明确要求“使用O(1)空间的迭代算法”递归版本其实是不能用的。后面我会专门展开对比。提示面试时如果题目里出现“原地”“就地”这类字眼先注意它的隐含要求。一般情况下都指向迭代法。2. 迭代三指针法最朴素也最标准的实现2.1 原理拆解为什么必须有三个指针先明确一个基础事实链表反转时我们要做的操作是让当前节点的next指向前驱节点。这个操作听起来不难但它会导致一个问题——你一旦改了当前节点的next原来的后继节点就找不到了。链表可不像数组没有索引可以帮你找回原来的下一个节点你唯一能访问下一节点的路径就是当前节点的next指针。所以我们在修改之前必须先把原后继节点“记下来”。这就自然引出了两个指针。一个用来保存原来的下一个节点可以叫next也可以叫nxt另一个用来指向已经处理好的前驱节点可以叫prev。再加上一个正在处理的当前节点curr一共三个指针。每次循环里做的事情非常简单用next保存curr的下一个节点。把curr的next指针指向上一个节点prev。将prev移动到curr。将curr移动到next。循环结束后所有节点的next都掉转方向prev恰好停在新链表的头节点。为什么要先保存next而不是先改指针顺序是整个算法最容易出错的地方。如果先执行curr-next prev那么原来curr后面那一截链表就彻底丢了你不可能再通过curr找到它。这一点我在给别人review代码时反复强调过大部分写错的人都是死在这一步。2.2 完整代码与逐步走查我用C和Python各写一版方便不同语言习惯的读者对照。逻辑完全一样只是语法不同。struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* next curr-next; // 先记住下一个节点 curr-next prev; // 掉转指针方向 prev curr; // 前驱向前走 curr next; // 当前节点向前走 } return prev; // 循环结束时 prev 就是新链表头 }class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverse_list(head: ListNode) - ListNode: prev None curr head while curr is not None: next_node curr.next curr.next prev prev curr curr next_node return prev用一个例子走一遍。假设链表为 1 - 2 - 3 - 4 - null。初始状态prev nullcurr 指向1。第一次循环next 指向21的next改为指向nullprev变为指向1curr变为指向2。这时以1为头节点的子链表已经反转完毕1 - null。第二次循环next 指向32的next改为指向1prev变为指向2curr变为指向3。这时处理完的部分是 2 - 1 - null。第三次循环next 指向43的next改为指向2prev变为指向3curr变为指向4。处理完的部分是 3 - 2 - 1 - null。第四次循环next null4的next改为指向3prev变为指向4curr变为null。第四次结束后curr为null循环退出。返回prev也就是4。链表变成 4 - 3 - 2 - 1 - null反转完成。关键点在于每次循环体内尾部的两条赋值是“记忆清除”的。prev和curr不是并列的而是curr要去“接管”被暂存的nextprev再去“接管”当前节点。这个接力顺序稍微一颠倒就会出错。2.3 复杂度与正确性证明时间上每个节点只被访问一次所以时间复杂度为O(n)其中n是链表长度。空间上只用了固定数量的指针变量因此空间复杂度为O(1)。证明这个算法正确可以用循环不变量来思考。每轮循环结束后存在这样一条状态以prev为头节点的子链表已经完成反转以curr为头节点的子链表仍是原始顺序等待处理。初始时这个不变量显然成立因为prev为null相当于一条空链而curr就是完整的原链表。循环中每一步都把curr的当前头节点摘下并挂到prev前面完成后不变量重新成立。当curr变为null时说明所有节点都已处理prev就是整条链表反转后的头节点。这个证明思路面试时不一定非要讲出来但自己能想明白写代码时心里就有底而不是背模板。3. 递归法和其他“看着对”但仓库不同的写法3.1 递归反转代码惊艳空间并不免费递归法的代码非常短思路也很优雅。递归函数先递归到链表的末尾然后逐层回溯把每个节点的next反过来指向前一个节点。递归完成后函数返回的是新的头节点也就是原链表的尾节点。先看代码ListNode* reverseListRecursive(ListNode* head) { if (head nullptr || head-next nullptr) { return head; // 空链表或者只剩一个节点直接返回 } ListNode* newHead reverseListRecursive(head-next); head-next-next head; // 让当前节点的后继反过来指向自己 head-next nullptr; // 断开当前节点与原有后继的连接 return newHead; }核心代码就三行递归反转指针断开。举例来说链表 1 - 2 - 3。reverseListRecursive(1)会等reverseListRecursive(2)完成而reverseListRecursive(2)会等reverseListRecursive(3)完成。3的next是null直接返回3。回到2这一层时执行2-next-next 2也就是3的next指向2同时2-next置为null。回到1这一层时2的next指向11的next置为null。最终结果是 3 - 2 - 1 - null。思路清晰代码简短但有一个致命缺点空间复杂度O(n)。递归深度就是链表长度如果链表有十万个节点系统栈可能会溢出。很多生产环境的代码规范都要求尽量避免深度递归原因就在这里。所以如果面试官允许递归写法它可以作为思路展示如果明确要求O(1)空间那就必须切换到迭代法。在工程系统里我更推荐迭代版本因为它稳定可控。3.2 头插法换个角度也是就地但别写错头插法是另一种反转方案从原链表的头节点开始一个一个摘下来然后以头插的方式重新挂到一个新的空链表上。因为每次都插到最前面最后形成的链表自然就是反转的。代码也不复杂ListNode* reverseListByHeadInsert(ListNode* head) { ListNode* newHead nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* next curr-next; // 先记录下一个节点 curr-next newHead; // 当前节点插到新链表头部 newHead curr; // 更新新链表头 curr next; // 继续原链表的下一个 } return newHead; }仔细看这段代码你会发现它跟三指针法在本质上非常接近。三指针法里的prev就是这里的newHeadcurr就是当前遍历指针next还是那个记录原后继的指针。只是视角不同三指针法强调在原链表上调整方向头插法强调把节点摘下后放到新链表的头部。从空间复杂度看头插法同样是O(1)空间没有新建节点只是重新排列了指针。所以面试时你写头插法一般也会被认为是就地算法。但头插法有个容易写错的地方插完当前节点后如果忘记用next保存原后继再次循环时连当前链表的下一个位置都找不到了。这部分和迭代法的思路是同构的所以我会优先建议只熟练掌握三指针法一种头插法理解一下就好写多了容易混淆思路。3.3 为什么不建议用数组辅助再回填总有同学会说我先把链表值全部取出来放到数组里反转后重新串起来不也能实现吗能但这个方法的空间占用是O(n)数组多大额外空间就多大。如果题目有空间限制或者你的服务同时要处理多条大链表这种写法会让内存压力骤增。而且它破坏了很多链表题的核心训练价值对指针的操控感。另外如果把数组里的值回填到原来的节点确实不需要新建节点但这已经背离了“就地反转”的本意。反转的本质是调整节点之间的连接关系而不是搬运数据。从工程角度看链表里的节点可能承载着外部引用外部结构可能还在通过这些节点访问数据直接改节点里的值会带来不可预知的副作用。所以在大多数场景下不要用数组辅助这种写法。4. 实战高频坑位这些错我见过太多次了4.1 指针顺序与丢失节点最典型的错误就是循环里没有先把next存下来直接执行curr-next prev。一旦你改了当前节点的next原来的后继节点就再也找不回来了。这在调试时表现得很诡异链表反转到一半后半截突然就消失了。其实不是内存坏了而是你亲手切断了唯一的访问路径。还有一种错误是顺序搞反先移动prev再保存next或者先移动curr再处理反转都会导致逻辑混乱。建议把下面这四步当成固定模板来记忆next curr.nextcurr.next prevprev currcurr next这四步的顺序不能变。第一步是为了保存后路第二步是为了执行反转第三步和第四步是把两个游标同时往前推进。只要第一步在前面后面三步怎么交换其实都能写出功能正确的代码但为了统一和可读性不要随意换序。4.2 边界条件与返回值边界条件的处理也是高频翻车点。第一空链表。如果head本身就是null循环根本不会执行直接返回prev也就是null这是对的。所以代码里不需要单独加if判断用自然逻辑就能兜住。第二只有一个节点的链表。循环执行一次prev变成原头节点curr变为null返回prev结果正确。第三返回值的问题。有的人在循环结束后习惯返回head那是不对的。循环结束时head仍然是原链表的头节点但在反转后的链表里它已经变成了尾节点它的next已经变成null。如果你返回head得到的是只有一个节点的子链表其他节点全丢了。正确的返回值是prev因为它才是反转后链表的头节点。这个坑在初写反转链表时出现频率极高务必记住。还有一点是关于“原来的头节点”。反转完成后原头节点变成新链表的尾节点它的next被置为null。如果代码里没有把它的next置空链表就会形成环。比如你只反转了一部分节点或者是从中间开始反转的忘记把尾部切断就会留下环路后续遍历会死循环。写代码时养成习惯任何节点一旦改变了next就要确认它指向的目标是正确的不能再指向原来的后继。4.3 调试技巧与测试用例设计链表调试比数组调试麻烦因为链表结构是隐式的不能用下标快速打印。我自己的习惯是用一个工具函数把链表从头到尾遍历把值都打印出来void printList(ListNode* head) { while (head ! nullptr) { std::cout head-val - ; head head-next; } std::cout null std::endl; }写反转算法之前先打印原链表反转后再打印一次一对比就能看出来哪里断了。如果发现链表输出出现循环也就是打印停不下来那多半是环路了。要快速定位是哪个节点出了问题可以增加一个计数器打印到比如100个节点时强行停止。另外也可以在纸上画出每个节点的地址调试时把指针的指向写出来。我在面试辅导中一直强调遇到链表题先在白板上画图确实能少犯很多错。建议测试时至少覆盖这几种情况空链表head null单节点链表1 - null双节点链表1 - 2普通链表1 - 2 - 3 - 4 - 5大量节点的链表比如1万个节点验证没有栈溢出问题迭代法不需要担心把这些场景都跑一遍基本能覆盖所有边界问题。5. 从面试题到工程现场反转链表不只是背代码5.1 面试官想考察的真正能力反转链表这道题几乎是算法面试里的“入门必修题”。面试官让你写它考察点往往不只是“会不会背代码”这一点。通常有三个层面。第一层是考察你对基本数据结构是否敏感。链表节点的构造、next指针的含义、节点的连接方式这些基础概念不清楚代码一定会出问题。第二层是考察逻辑拆解能力。能不能把一个总目标“反转整个链表”拆成“逐个调整相邻两个节点的指针方向”这样一个可循环的单元操作。这其实是很多工程问题里都会用到的思考方式把大问题化成一个固定的迭代步。第三层是考察边界感。空链表、单节点、返回值等边界情况如果你能在没被提示的前提下主动答出来面试官会认为你平时写代码是有安全意识、考虑过边界异常的人。这一点在真实工程里很重要。所以不要抱着“刷题”的心态去背代码。每写一次就动笔在纸上把每一步的执行过程画一遍画几遍之后你会形成肌肉记忆甚至能自己推理出变体题的做法。5.2 它在真实项目里出现的几个位置链表反转在一些基础组件和业务场景里确实会用到我举几个常见的例子。浏览器或文档编辑器的撤销操作常常用链表来记录操作序列。当你执行“撤销”时需要把最近一次操作移到某个位置链条顺序可能要反转。栈结构虽然能解决一部分问题但当撤销和重做两个方向都要支持而且需要保持历史顺序时链表的灵活性就体现出来了。此时如果需要在链表的任意区间进行反转那正是“区间反转链表”的用武之地。缓存淘汰算法里也会遇到类似的指针重排。比如LRU缓存用双向链表维护访问顺序每次命中一个节点就要把这个节点从当前位置摘下来移动到头部。这里面没有任何“反转整个链表”的动作但摘节点、插入头部、移动节点这些基础操作抽象来看都是指针方向的调整和重接原理和反转链表高度一致。再说一个更底层的场景。操作系统里管理进程、管理内存块时经常用链表组织对象。某些场景下比如要倒序扫描一个对象列表与其额外开一块内存存索引不如就地反转这个链表。这种地方O(n)额外空间可能会直接让内存吃紧所以才更需要就地算法。5.3 以“反转链表”为支点可以演化出的变体题反转链表学透了一连串的变体题都会变得好理解。第一个变体是反转链表的指定区间。比如要求只反转从第2个节点到第4个节点之间的部分。解法是定位到区间的前一个节点然后对这个子链表做反转最后把子链表接回原链表。实现时要注意区间的起点和终点以及边界情况是m1还是n链表长度。很多复杂链表题都建立在“局部反转”这个动作上。第二个变体是K个一组反转链表。题目要求每K个节点反转一次每次反转内部用的依然是三指针法只是每处理完一组就要重新设置prev边界。这个题对代码组织能力要求更高但核心单元操作没有变。第三个常见变体是判断回文链表。算法用快慢指针找到中点然后反转后半段再比较两半是否相等。这里就实实在在使用了“反转链表”的子过程。写一次回文链表判断你就会意识到反转操作在链表算法中的地位。第四个变体是两两交换链表中的节点。每两个相邻节点换一下位置也可以看成是K等于2的K个一组反转。核心手法依然是三指针法的变体。把这些放在一起看反转链表确实是链表操作的地基。所以多花点时间把这个基础算法吃透后面刷题会顺畅很多。提示想检验自己是否真的掌握可以试着不看代码给一个任意长度的链表在白板上画出来每一步操作然后用代码实现。如果画图和写码都能顺利完成就算真正过关了。最后分享一个我个人的习惯。带团队协作时我要求新人提交链表相关代码前必须自己先构造三组测试用例最小边界、正常规模、规模大一点的场景。即使语言自带内存管理也要想清每个指针在每一轮循环后指向哪里。这种较真的习惯帮我们在生产里避免过很多次潜在的内存问题。反转链表虽然只是一道“入门题”但把它的每一步思考内化成肌肉记忆后面你会感谢这段基础训练。