★ FEATURED ARTICLE 前两天在后台收到一条留言“反转链表这种烂大街的题为什么每次一写就崩”我反手问了一句“你能不背代码在纸上把三个节点反转的指针变化画出来吗”对方沉默了。反转链表是数据结构里最基础的指针操作也是最容易被低估的一道题。很多人不是不会逻辑而是没搞懂就地反转的指针流动过程只会照着模板抄。这篇文章不打算再给你一个代码让你背而是把就地反转的每一步掰开揉碎从迭代三指针、递归调用栈讲到部分区间反转的边界处理再补几个实实在在的调试方法。适合刚开始学链表的同学也适合准备算法面试的朋友。1. 想清楚就地反转到底在做什么1.1 什么是“就地”为什么这个问题被面试官偏爱先说结论就地反转的意思是不申请任何与链表节点数量相关的新内存只靠修改节点之间的next指针方向把整个链表的顺序倒过来。比如原来1 - 2 - 3 - NULL反转后变成3 - 2 - 1 - NULL。注意是“改指针”不是“改值”。有人会问我把每个节点的整数 val 都换成对应位置的值不也行吗行但那不是链表操作的意义而且你依然可能需要额外的容器来存值如果节点内部还有动态分配的复杂字段拷贝代价会非常高。面试官偏爱它是因为这道题能一次性考察几个关键点你是否理解指针就是“地址的别名”、你是否能手动模拟指针变化、你是否关注边界条件空链表、单节点、你写的代码空间复杂度是否达标。很多人背下代码能写对但被追问一句“为什么循环结束后返回 prev 而不是 cur”就卡住说明根本没理解指针在怎么走。这里也有一个容易混淆的点“就地”不代表不能使用局部变量。你当然要准备几个指针变量它们占固定几个字节属于常数空间。判断是否就地看的是额外空间复杂度是否为 O(1)。如果反转链表时要新建一个数组或一整个新链表那叫 copy 式反转不是就地。1.2 深入指针流动用“三指针”看本质单链表反转最成熟的思路是三指针法三个指针分别叫prev、cur、next。它们是某种意义上的“过去、现在、未来”。用一个生活化的类比假设一个班的学生排成一列前后手拉手现在要让整列掉头。你不能去找另一批人来替换他们只能让学生一个一个地转身。每当你让第一个人转过身去握住前一个人时他原来握住的那只手就会松开所以你必须让某个旁边的人先帮你“盯着”那个人否则就找不到了。链表里也一样next指针就是那个帮你盯住后面节点的人。具体的循环逻辑是这样的最开始prev NULLcur head。因为第一个节点反转后要变成尾节点它的next最终必须指向NULL。只要cur不为空就做四步操作用next保存cur-next防止下一步修改cur-next之后后面的节点丢失。把cur-next改成指向prev。把prev指针向前移到cur。把cur指针向前移到next。循环结束时cur是NULL说明已经遍历完所有节点此时prev停留在原链表的最后一个节点上它也就是反转后链表的头节点所以return prev。这套操作的每一步都有明确目的。为什么要先保存next因为一旦执行了cur-next prev原来的后继关系就被破坏了如果不先留个副本你后面根本不知道下一个该处理谁。为什么要移动prev和cur因为下一次迭代时当前的cur要变成新的前驱刚才的next要变成新的当前节点。如果不移动循环就原地打转了。2. 迭代实现三指针从思路到代码2.1 C语言实现每个指针为什么这么动核心代码非常短但每一行都不能乱。我用 C 语言写一遍#include stdio.h typedef struct Node { int val; struct Node *next; } Node; Node* reverseList(Node* head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; // ①保存后继 cur-next prev; // ②反转next指针 prev cur; // ③prev前进 cur next; // ④cur前进 } return prev; // 新链表头 }很多人第一次看这段代码觉得“太简单了”然后就跳过这是最亏的。注意代码的顺序一定是先next cur-next再cur-next prev。如果你先写cur-next prev那么原来的cur-next就被覆盖了下一步cur cur-next会让 cur 跑回 prev 那边链表断成两截。prev初始化为NULL也很有讲究。这是为了让原链表的第一个节点成为反转后的最后一个节点而最后一个节点的next必须是NULL。如果初始化为head或者别的值新链表尾巴会指到一个不该指的位置轻则遍历越界重则形成环。如果链表带头节点情况略有不同。多数教材里说的反转针对的是不带头节点、直接由数据节点构成的链表。如果是带头节点的链表头节点本身不存储数据你要反转的是头节点之后的整段数据节点并让头节点的next指向新的第一个节点。这时常见做法是先取head-next作为需反转的起点反转完成后让head-next newHead。如果忽略这个差异直接对带头节点调用上面的函数等于把无用节点也反转进去结果就错了。2.2 纸上推演一个三步示例彻底看懂指针顺序纸上模拟是学习指针操作最有效的方法没有之一。我们用1 - 2 - 3 - NULL举例完整跑一遍。初始状态prev NULLcur 1。链表1 - 2 - 3 - NULL。第一轮循环next cur-next 2cur-next prev也就是1 - NULL链表状态暂时为1 - NULL2 - 3 - NULL。注意这是人脑视角的“分叉”但实际内存里 2 和 3 还在并没有丢失只是 1 和 2 之间的链接被切断了。prev cur即prev 1cur next即cur 2第二轮循环next cur-next 3cur-next prev也就是2 - 1链表状态2 - 1 - NULL同时3 - NULLprev 2cur 3第三轮循环next cur-next NULLcur-next prev也就是3 - 2链表状态3 - 2 - 1 - NULLprev 3cur NULL循环结束返回prev 3。如果你把上面的过程画在一张纸上会发现prev和cur像是两个探针一步一步从左往右挪而节点的next方向被一点一点从右往左翻过来。这就是三指针反转最直观的画面。手动模拟建议至少做三个例子空链表、单节点、四个节点的普通链表。空链表返回NULL单节点head-next为空循环一次都不进返回prev NULL这里要注意prev初始是NULL单节点时cur headnext NULL进入循环后执行反转最终返回prev head。所以单节点也能正确处理。多节点则能暴露顺序问题。2.3 复杂度分析为什么就地迭代是最优解时间上每个节点只被访问一次做常数次指针操作所以时间复杂度为 O(n)。空间上只用了三个指针变量不管链表多长占用空间都是固定的常数大小所以额外空间复杂度为 O(1)。这已经是链表反转的最优解了因为你需要遍历所有节点不可能跳过任何一个。有些解法会先把链表的值依次存入一个数组反转数组后再重新填回节点。这实现起来思路简单但空间复杂度是 O(n)而且多做了两轮遍历实际中几乎不会这么写。对于存有大量数据的节点数组拷贝的内存开销和性能损耗都是不可接受的。因此面试官只要听到你指出的“数组法不是就地”一般就会认可你对复杂度的理解。有人会问“就地”是不是意味着连常数空间都不能用当然不是。所谓原地操作指额外空间与输入规模无关不会因为链表越来越长而申请越来越多内存。这点在面试时最好主动讲清楚能体现你对复杂度定义的准确把握。3. 递归实现从后往前改的另一种思路3.1 递归版的代码与终止条件递归写出来的反转代码比迭代更短但对新手来说也更难理解。先看代码Node* reverseListRec(Node* head) { if (head NULL || head-next NULL) { return head; } Node *newHead reverseListRec(head-next); head-next-next head; head-next NULL; return newHead; }这里的核心假设是调用reverseListRec(head-next)之后从head-next开始的那一段子链表已经被整体反转并且返回的newHead是这个子链表的新头。比如当前head 1head-next 2递归处理2 - 3 - NULL后得到的子链表变成3 - 2 - NULL返回的newHead 3。那么原链表还剩下什么关系head-next仍然是 2也就是说当前 1 还指向 2而反转后的 2 已经变成了整个子链表的尾节点它的next是NULL。我们要把当前节点 1 接到这个尾巴后面就要执行head-next-next head也就是让 2 指向 1。然后执行head-next NULL让 1 成为新链表的尾节点。最后返回newHead也就是 3。这里最反直觉的地方是“递归调用之后head-next 到底是谁”。很多人以为head-next已经被改变了其实没有。在递归调用前当层函数的head-next还指向它的后继节点递归调用只处理了后继节点之后的链路没有动当前节点和这个后继之间的那根指针。所以head-next-next head才是安全的。如果你理解成了别的顺序很容易写出head-next head-next-next之类的错误。3.2 递归的空间复杂度到底算不算“就地”递归版本没有显式创建节点从“是否申请新节点内存”的角度看它似乎也是就地。但从算法分析的角度递归每深入一层系统调用栈就要压入一层栈帧保存当前函数的局部变量和返回地址。链表有 n 个节点递归深度就是 n 层空间复杂度是 O(n)。因此如果题目要求“常数空间原地反转”递归版本不符合要求。在面试和工程里这两者的差别很实际。链表长度达到几千甚至几万时递归调用栈可能把程序栈撑爆直接栈溢出崩溃。相比之下迭代的三指针方案无论链表多长都用固定变量没有这种风险。所以现在很多公司的面试题会特意强调“迭代实现”就是为了考察你能不能避开递归的额外空间。不过递归并不是一无是处。它把问题拆成“先反转除了头节点以外的子链表再把头节点接到末尾”逻辑非常清晰特别适合用来向别人解释“反转”这个概念。代码只有四行也不太容易写出悬空指针。所以面试时你可以先用递归版本讲思路然后立刻补一句“但如果要求常数空间我会用迭代。”然后写出迭代代码。这也是展示自己既能理清思路、又能解决工程约束的好方式。3.3 迭代和递归面试时怎么选对比维度迭代三指针递归法代码长度略长逻辑直白更短但理解成本高空间复杂度O(1)O(n) 调用栈栈溢出风险无链表过长会溢出指针操作直观度高适合现场推演低抽象但有规律面试推荐度必须掌握可作为补充解法我在实际经验中的建议是先掌握迭代因为它是最符合“就地”要求的解法。递归作为知识拓展最好也练熟因为你不能保证对方不会追问“你还能用递归写吗”。两种都练到能盲写再去面试就会淡定很多。还有一个隐藏的好处当你理解了递归回头再看迭代往往会更清楚为什么返回prev、为什么第一步必须保存next。4. 变体与延伸反转一段链表、头插法和其他结构4.1 反转部分链表边界条件比主函数还难反转整条链表只是入门更常见的是反转某一段区间。例如给定链表1 - 2 - 3 - 4 - 5要求反转第 2 个节点到第 4 个节点之间的部分期望结果变成1 - 4 - 3 - 2 - 5。这种题的核心在于处理好区间前后的连接。如果用普通反转整链的思路很容易把区间外部分搞丢。我常用的方法是引入一个哑节点dummy让dummy-next head这样可以统一处理“区间从第一个节点开始”的情况避免反转后头节点改变导致返回值混乱。然后用两个步骤完成先让一个指针pre走到第 m-1 个节点这个pre就是区间前一个节点。对区间内的节点做若干次“摘下一个节点插到 pre 后面”的操作也就是头插法。C 风格代码如下Node* reverseBetween(Node* head, int m, int n) { Node dummy; dummy.next head; Node *pre dummy; for (int i 1; i m; i) { pre pre-next; } Node *cur pre-next; for (int i 0; i n - m; i) { Node *next cur-next; // 要摘下的节点 cur-next next-next; // 跨过 next next-next pre-next; // 插到 pre 后面 pre-next next; // pre 重新指向它 } return dummy.next; }这段代码看着和整链反转不太一样但核心思想一致每次把当前区间内靠后的节点提前到区间头部逐步让区间内部倒序。为什么第二个循环次数是n - m而不是n - m 1因为区间内有n-m1个节点第一个节点作为“新尾部”不需要移动只需把剩余n-m个节点依次摘到前面来。这个细节非常容易弄错写完后建议代入m2, n4的六节点例子手动跑一遍。4.2 头插法另一种就地反转的姿势除了三指针还有一种常见的遍历式反转叫做头插法。它的思想是不断把当前节点从原链表中“摘”下来然后插入到新链表的头部。如果使用带头节点的链表作为辅助代码可以这样写Node* reverseByHeadInsert(Node* head) { Node *dummy malloc(sizeof(Node)); dummy-next NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; cur-next dummy-next; // 把 cur 接到新链表的头部 dummy-next cur; cur next; } Node *newHead dummy-next; free(dummy); return newHead; }这里dummy是一个临时头节点不参与数据。好多人第一次看到会觉得“这不又多了一个节点吗”其实dummy是我们在栈上或堆上申请的一个单独节点对象空间只有 O(1)不会随着链表长度增长所以它没有破坏就地的内涵。当然如果你不想用dummy也可以用prev指针模拟但逻辑会更绕一点。头插法和三指针法的本质是一样的区别在于“新链表头”的表示方式。三指针法用prev表示已经完成反转的部分头插法则用dummy-next指向已经完成反转的部分。理解了这一点你就不会觉得它们是两种完全无关的写法。在做部分区间反转时头插法反而更顺因为它的插入位置固定可以精确控制在某个节点后面。4.3 就地思想能延伸到哪双链表反转和内存友好单链表反转是“就地操作”的代表作但这份思想不止于单链表。双链表反转只需要遍历一次把每个节点的prev和next指针交换然后返回新的头原来是尾。代码量更少因为两个方向都有指针不用担心断链后无法找回下一个节点。不过双链表更常被问“为什么不直接用prev”这里不展开但思路是相通的。更广地看就地算法强调的是“动手改造现有结构而不是复制一份再处理”。这种思维在嵌入式系统、操作系统内核、内存管理器里都有体现。比如你有一大块连续内存被划分成空闲块链表当需要整理空闲块顺序时你不会重新分配一堆节点来保存新顺序而是在原链表上改指针。掌握了链表反转的指针操作手感再来读那些源代码会觉得亲切很多。5. 常见问题与调试技巧实录5.1 典型错误链表断了一半、只剩一个节点我自己看过太多人写反转链表出错方式主要集中在下面几种忘记先保存next。这是最常见的。直接写cur-next prev;之后再用cur cur-next移动结果 cur 跑到了 prev 那边链表从中间断开。循环条件写成while (cur-next ! NULL)。如果cur是NULL这里会直接解引用空指针就算没空指针循环停止时最后一个节点还没有被处理反转不彻底。返回cur而不是prev。循环结束时cur是NULL返回它等于返回一个空链表这是“反转后什么都没有”的常见原因。把head-next和prev混用。有人试图用head-next作为遍历游标结果越改越乱。忘了把原头节点的next置空。如果prev初始不是NULL而是一个别的指针就会导致新链表尾部有诡异链接。如果你发现运行结果里只输出一个节点大概率是第二步和第三步顺序搞错或者prev、cur初始化不对。不妨在循环里加一行打印输出当前的 prev 和 cur 的值立刻就能定位。5.2 指针看不见如何在本地快速验证调试链表不像调试一把数组那么直观我常用的方法是三件套打印链表、断言关键条件、用最小用例对比。打印遍历很朴素但有用。可以写一个printList函数每次循环迭代后打印当前链表状态或者在反转前后各打印一次。最好给每个节点编号例如打印(1)-(2)-(3)这样你能清楚看到中间状态。还建议加断言assert验证不变式。比如反转过程中prev始终指向已经反转部分的头节点cur始终指向尚未反转部分的头节点还可以断言节点数量不变不会出现少节点的情况。灵活运用测试用例。不要只测常规的三节点链表把空链表、单节点、双节点、已反转的链表都测一遍。如果有一个对照实现比如“先用数组记录值再逆序写入”的版本你可以在同一个随机生成链表的用例下反复对比结果。虽然那个版本不是就地算法但它能作为正确性的参照。终极方法还是动手画。用纸笔画一个四节点链表把指针画成箭头每执行一步就擦掉旧箭头画新箭头。看似原始但真的能治好“读代码头晕”的毛病。我见过不少程序员的困惑往往不是代码问题而是脑子里没有一张清晰的指针变换图。5.3 面试追问应对链表有环怎么办、还能优化吗面试官不会满足于你写出一段能跑通的代码。常问的追问有这么几个第一个递归版和迭代版的区别答案参考前面的复杂度分析直接说迭代是 O(1) 空间递归有 O(n) 栈空间长链表可能栈溢出。第二个如果链表里可能有环怎么办这时候必须提醒面试官反转链表的前提是输入链表无环。如果链表有环且反转时不处理那么反转后的链表可能依然是环甚至会出现一个环加一条尾巴的诡异结构。你需要先做环检测比如快慢指针确认无环后再反转。不要假装能直接反转环。第三个还能在时间和空间上更进一步优化吗答案是不能因为时间必须 O(n)空间必须 O(1) 才最省。如果你说“可以再优化到 O(log n)”那一定是不理解问题。这种追问其实是在考你对自己代码复杂度的认知。第四个如果要求“不能修改原链表”你会怎么做那你只能做复制式反转不可能就地但面试官可能想听你分析需要 O(n) 空间和 O(n) 时间并解释为什么。遇到连环追问时我自己的习惯是先回答“这道题的本质是改变指针方向不是复制数据”然后把上面几个点依次铺开。只要思路清晰哪怕笔试时代码有点小错面试官也会愿意引导你补上。把反转链表的迭代写法练到条件反射之后有个小习惯特别值得养成写完后立刻在代码旁边把四个节点的指针变化画出来确认每一步的 prev、cur、next 都符合预期。这个习惯帮我在代码评审时抓出过好几次用递归处理超大链表导致的隐患。希望这篇能把你在指针上的那点“不踏实”彻底扫清。
阅读完成 · 觉得有帮助？
