要说面试里出现频率最高的链表题反转链表排第二估计没谁敢排第一。我当年准备校招的时候第一次看到这道题内心是有点懵的——明明代码就那么几行为什么一上手不是段错误就是死循环后来刷多了才明白这道题考察的根本不是“能不能背出答案”而是你是不是真的理解指针是怎么把一个节点串起来的以及改动指针方向时哪些瞬间会丢节点。这篇就用C语言把剑指 Offer 24 讲透。核心内容包含三种解法——迭代法、递归法、头插法——以及我在本地调试时踩过的各种边界条件的坑。不管你是刚接触链表的小白还是正在冲刺面试的求职者这篇文章的目标只有一个让你看完之后能独立手写出这段代码并且敢在面试官面前讲清楚每一步在干什么。1. 为什么面试官都爱考这道题一次考察三种底层能力很多新手不理解反转链表这么“简单”的题为什么能成为剑指 Offer 的高频题。我在准备面试阶段刷了上百道题之后最大的体会是这道题表面上考的是链表翻转实际上考的是三件更底层的本事——指针操作的手感、边界条件的敏感度、递归思想的熟练度。这三个能力恰恰是做任何 C/C 项目都绕不开的基本功。1.1 链表结构体定义与基本打印逻辑先把最基础的准备做扎实。C语言里单链表的节点定义几乎是固定的面试时直接默写struct ListNode { int val; struct ListNode *next; };光有节点还不够我习惯先在本地把“打印链表”这个辅助函数写好。别小看这个动作调试链表题时你每次都靠它确认反转结果对不对省下的时间远比写的几分钟多。void printList(struct ListNode *head) { struct ListNode *cur head; while (cur ! NULL) { printf(%d , cur-val); cur cur-next; } printf(\n); }创建一条简单测试链表struct ListNode* createTestList() { struct ListNode *n1 (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *n2 (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *n3 (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *n4 (struct ListNode*)malloc(sizeof(struct ListNode)); n1-val 1; n1-next n2; n2-val 2; n2-next n3; n3-val 3; n3-next n4; n4-val 4; n4-next NULL; return n1; }这段测试代码看起来很笨但它对初学者的好处是每个节点的内存都清清楚楚你能直观看到指针之间是怎么连接的。很多搞不懂反转的人不是不理解算法而是根本不熟悉链表的“物理结构”。1.2 这道题在面试题体系中的“地基”位置反转链表之所以被反复考还因为它是很多复杂链表题的基础零件。你不信的话可以想想这几道题整个链表反转、反转链表的前N个节点、区间反转、K个一组反转链表、回文链表判断……这些题的核心思想都建立在单链表反转这一个操作上。拿K个一组反转来举例它其实就是在链表上分段做反转每段的内部反转方法和剑指 Offer 24一模一样。也就是说如果你能把这个基础版写得既快又对后面做进阶题时你只需要把注意力放在“每一段的边界怎么衔接”而不用再纠结反转本身怎么写。地基打得稳往上盖楼才不慌。我自己的建议是练习时不要只满足于“调通了”而是要把迭代法、递归法、头插法都写一遍并且每个版本都讲得出“为什么这样写”。下面几个章节我分别把三种解法拆开聊。2. 迭代法三个指针轮流“调头”一步步把箭头掰过来迭代法是我面试时最优先写的解法。理由很简单时间复杂度 O(n)、空间复杂度 O(1)思路直白不容易写崩。它本质上做的一件事是遍历链表的过程中逐个把每个节点的 next 指向前一个节点同时用额外的指针保住“下一个要处理的节点”。2.1 三指针思路与代码实现核心操作可以概括成一句话prev 指向当前节点的前一个cur 指向当前节点next 暂存 cur 原本的下一个节点。每轮循环把 cur-next 改成 prev然后三个指针集体往前挪一格。struct ListNode* reverseList_iterative(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *cur head; struct ListNode *next NULL; while (cur ! NULL) { next cur-next; // 先保存下一个节点防止断链 cur-next prev; // 当前节点掉头指向前一个 prev cur; // prev 前移 cur next; // cur 前移 } return prev; }这里最需要注意的是next cur-next;这一行。我第一次写的时候漏掉了它直接把cur-next prev写上去结果链表从第一个节点开始就断掉了——因为原来 cur-next 指的那个节点没有任何变量还指向它谁也找不回去了。你可以把链表想象成一列手拉手的人现在第一个人要回头牵住身后的人那就必须先用另一只手拉住第二个人否则第二个人就掉队了。2.2 为什么 prev 初始化为 NULL 而不是 head很多初学者会问prev 为什么不初始化为 head我先不直接回答请你想象一下链表反转完之后原来第一个节点的 next 应该指向谁答案是 NULL因为它变成了新的尾节点。所以 prev 一开始就是 NULL当循环走到最后时prev 恰好会停在原来的最后一个节点上而且这个节点的 next 已经被修改为它的前一个节点没有残留的野指针。另外prev 从 NULL 开始还能顺带处理一个特殊情况如果传入的是一个空链表head 本身是 NULL循环一次都不执行直接返回 prev也就是 NULL。这个写法干净利落地把空链表和单节点链表的情况一并解决了。单节点链表也是同理cur-next 指向 NULL反转后还是那一个节点不会出问题。2.3 本地完整测试把算法跑起来才算学会光看代码不运行和没学区别不大。我把测试代码补全你复制到本地就能看到效果int main() { struct ListNode *head createTestList(); printf(反转前: ); printList(head); struct ListNode *reversed reverseList_iterative(head); printf(反转后: ); printList(reversed); return 0; }输出结果应该是反转前: 1 2 3 4 反转后: 4 3 2 1我建议你把printList加进循环里每反转一步打印一次当前链表状态。这样你能亲眼看到节点一个接一个“掉头”的过程比单纯盯着脑内推演要直观得多。我当时就是这么干的打印几次之后再也没忘记过三指针的移动顺序。2.4 一个常见的笔误cur 和 next 的赋值顺序我见过不少人包括我自己早期把循环体写成了这样next cur-next; cur-next prev; next cur; // 笔误应该是 prev cur prev next; // 笔误顺序乱了这种错的离谱的写法表面上看起来逻辑很“像”跑起来却会得到完全不同的结果甚至死循环。我的经验是三指针移动的时候眼睛要盯着“谁应该成为新的 prev谁应该成为新的 cur”。记住一个口诀先断后接再人齐步走——先处理 cur-next 的指向再用 next 带着 cur 往前走prev 紧跟其后。3. 递归法让指针在“原路返回”的过程中回头递归解法在代码量上比迭代法还要短但理解门槛高不少。很多教程直接甩代码然后说“这个递归压栈再弹栈就好了”听懂了也只是似懂非懂。这一节我会用两种递归写法来拆重点讲清楚每一步回溯时到底发生了什么。3.1 理解递归的关键先递到链尾再归中改指向先看最经典的递归写法struct ListNode* reverseList_recursive(struct ListNode* head) { if (head NULL || head-next NULL) { return head; } struct ListNode *newHead reverseList_recursive(head-next); head-next-next head; head-next NULL; return newHead; }这段代码的核心逻辑只有两行head-next-next head;是把当前节点的下一个节点的 next 指回当前节点也就是完成一次“反向钩连”。head-next NULL;是为了让当前节点当前处于链表尾部相对回溯过程而言时不再指向原来的下一个节点防止形成环。许多人的困惑在于“newHead 到底是从哪来的”答案来自递归的终止条件当递归递到链表的最后一个节点时head-next NULL直接返回这个节点。这个节点就是整个链表反转后的新头节点。它会被一层层原封不动地传回去所以代码里return newHead;是一条“接力棒”路径不是在每层生成新东西。3.2 一条四节点链表的手推全过程我们拿 1→2→3→4 来走一遍reverseList_recursive(1) 进入head11-next 不是 NULL调用 reverseList_recursive(2)reverseList_recursive(2) 进入head22-next 不是 NULL调用 reverseList_recursive(3)reverseList_recursive(3) 进入head33-next 不是 NULL调用 reverseList_recursive(4)reverseList_recursive(4) 进入head44-next 是 NULL返回 4到这里“递”的过程结束开始“归”的过程回到调用者 head3 的那一层head-next是 4执行4-next 3再把3-next NULL返回 newHead4回到调用者 head2 的那一层此时 3 的 next 已经变成 NULL但 head-next 仍然指向 3所以执行3-next 2再把2-next NULL返回 newHead4回到调用者 head1 的那一层此时 2 的 next 已经是 NULL但 head-next 仍然指向 2执行2-next 1再把1-next NULL返回 newHead4最后从函数外面拿到的 newHead 就是节点 4从 4 出发依次是 3、2、1反转完成。这个过程我建议你也亲手在纸上画一遍箭头改来改去的样子很像在做手工折纸——每次把折好的方向调转一次。画过一遍之后你对递归的理解会比背十遍代码都深刻。3.3 递归解法版本二自顶向下返回值携带新头还有另一种递归写法它的思路是“把当前节点放到已反转链表的头部”方向是从前往后处理。这种写法稍微绕一点但对理解递归返回值很有帮助struct ListNode* reverseList_recursive2(struct ListNode* head) { return reverseHelper(head, NULL); } struct ListNode* reverseHelper(struct ListNode* cur, struct ListNode* prev) { if (cur NULL) { return prev; } struct ListNode *next cur-next; cur-next prev; return reverseHelper(next, cur); }这个版本本质上是用递归的形式做了迭代法的事情把 prev 作为参数一路传递下去当前节点 cur 的 next 直接改为 prev然后递归处理原来的 next 节点。它避免了显式写循环但又和迭代法的思路完全一致。面试时如果你的递归版写得够熟练也可以顺带提一句这个自顶向下的写法展示你对递归和迭代关系的理解。3.4 递归和迭代怎么选一个务实的判断标准我自己的选择标准很朴素如果只是解这道题用迭代如果聊到递归思想用版本一如果想展示对“递归携带状态”的掌握可以用版本二。但必须提醒你一个实际问题递归版本在链表很长的时候会有风险。C语言的栈空间有限链表长度达到几十万甚至上百万节点时递归深度过大会导致栈溢出。所以面试场景下如果题目没有特别说明“允许递归”我建议默认先给迭代解再把递归解作为补充方案讲解。这样既保证了代码的健壮性又展示了你对两种思路都吃得透。4. 头插法与边界条件从 Dummy Node 到空链表所有坑一次排完第三类常见解法是“头插法”。它的思路是新建一个哑巴节点dummy node作为哨兵遍历原链表把每个节点拆下来插入到 dummy 节点之后。最终dummy-next 就是反转后的新链表头。4.1 头插法代码实现struct ListNode* reverseList_headInsert(struct ListNode* head) { struct ListNode dummy; dummy.next NULL; struct ListNode *cur head; while (cur ! NULL) { struct ListNode *next cur-next; // 暂存剩余链表 cur-next dummy.next; // 当前节点指向新链表头 dummy.next cur; // 更新新链表头为当前节点 cur next; // 继续处理剩余链表 } return dummy.next; }注意这里的dummy我是直接定义在栈上的结构体变量而不是用 malloc 分配。原因很简单这个节点的唯一作用是提供“插入位置的前驱”不需要长期存活用完即弃。用栈上变量还能省掉手动 free 的麻烦代码也更干净。如果你喜欢也可以用 malloc 分配一个struct ListNode *dummy (struct ListNode *)malloc(sizeof(struct ListNode));但记得在返回前 free 掉否则就有内存泄漏。4.2 头插法的适用场景理解它的“原型”反而更好进阶说实话单就这道题而言头插法不是主流答案。但理解头插法对后续很多题目帮助很大。举个例子经典的两两交换链表节点、重排链表等问题都需要“从原链表拆除一个节点再插到另一个位置”的能力。头插法练熟了你会形成一种“拆装节点”的肌肉记忆——先存 next再修改指针再移动 cur。而且头插法有一个迭代法不具备的心智模型它在持续构建“一段已经反转好的新链表”新链表的头始终在 dummy-next。这种“边遍历边构建新链表”的思维也是链表排序题如插入排序的底层逻辑。所以即使不常用我也强烈建议你写一遍。4.3 边界条件清单空链表、单节点、双节点、大链表我最近在做题目复盘时把边界条件整理成了一个小清单每次写完反转代码都用它来自检场景预期结果容易踩的坑空链表 headNULL返回 NULL循环不会执行注意返回值别写成野指针单节点链表返回原节点确保该节点的 next 变成 NULL双节点链表返回原第二个节点注意原头节点的 next 必须置空长链表全部倒序防止递归版本栈溢出优先用迭代链表有环理论上不会有死循环可思考该算法为什么能检测出环其实不能最后一行“链表有环”虽然在题目约定下不会出现但我在实际面试追问环节被问过“如果链表带环会怎样”。我当时答得不够好这里提醒你迭代法面对有环节点时cur 永远不会走到 NULL循环不会结束。所以在真实工程中如果你不确定链表是否干净先做环检测再说。4.4 内存管理的细节C语言版本绝不能漏掉的问题这道题用 C 语言写还有一个需要留意的点反转操作本身不改变节点的数量也不会新分配节点。所以在纯反转场景下你不需要考虑 free 每个节点。但如果你的测试代码里像上面的 createTestList 一样用 malloc 建了一批节点那在测试结束后最好把它们都 free 掉避免内存泄漏。调试阶段的习惯也很重要printList之后遍历完链表注意别对已经 free 的节点再访问。我曾经因为先 free 再 print 的顺序搞反直接触发了“use after free”排查了半天才反应过来。后来我把辅助函数都统一成“先打印、后释放”的顺序再也没出过这类问题。5. 面试现场的完整应对思路从白板画图到 Bug 复现算法题刷得再多面试时如果表达不清楚效果都会打折扣。我在经历了几轮真正的技术面之后最大的感受是面试官真正想看的不是答案而是你思考问题的路径。所以反转链表这道题准备的不应该是“背代码”而是一套可以现场展示的解题流程。5.1 动笔之前的固定动作先画链表再标指针我每次面试遇到链表题都会先画一个至少包含三到四个节点的链表图节点用方框表示next 用箭头表示。然后在这条链表上方标出三个位置prev、cur、next。接着逐步演示第一轮循环怎么改箭头方向第二轮怎么移动指针。这个动作看似浪费时间实际上有双倍收益一方面帮你自己理清思路减少写代码时的手忙脚乱另一方面让面试官看到你是“有结构地思考”而不是“硬背答案”。我遇到好几个面试官在我画图时频频点头后面追问的问题也明显友善了很多。5.2 一套可以现场复现的自测用例写完代码之后千万别直接说“写完了”。我在最后一次找工作时学到的是主动提出“跑几个用例验证一下”。面试官通常会让你口头走一遍你可以按这个顺序来空链表head 是 NULL循环体不执行直接返回 NULL。单节点一系列 1→NULL循环执行一次返回原节点。普通链表1→2→3走完三轮。如果面试官让你在白板上写完整的 main 测试也完全不用慌把 createTestList 和 printList 写出来就行。能当场写出测试代码是很加分的行为因为这表明你不只会写算法还知道怎么验证结果。5.3 进阶追问的延伸思考反转前 K 个节点与区间反转面试官很可能在你写出基础反转后追问一句“那反转前 K 个节点你会吗”这个问题其实是剑指 Offer 24 的直接变体。思路和迭代法一致只是只循环 K 次反转前 K 个节点。反转完成后原来的第 K1 个节点需要接在链表末尾所以代码里要保存一下原链表的“后续部分”struct ListNode* reverseK(struct ListNode* head, int k) { struct ListNode *prev NULL; struct ListNode *cur head; struct ListNode *next NULL; for (int i 0; i k cur ! NULL; i) { next cur-next; cur-next prev; prev cur; cur next; } // 此时 head 是反转后的尾节点它的 next 应接上 cur if (head ! NULL) { head-next cur; } return prev; }然后如果把这个基础版再升级成区间反转比如反转第 m 到第 n 个节点思路就是先找到前驱节点然后对区间内部做同样的反转再把前驱和区间尾接好。你会发现所有升级版的核心零件还是今天这道题。这也就是我开头说的“地基”含义。5.4 我自己刷这道题的真实体会回头来看反转链表是我刷题阶段“从背答案到懂答案”的转折点。刚开始我只能默写迭代法面试被问“为什么 next 要先保存”时我只会说“怕断链”但根本讲不清断链的瞬间发生了什么。后来我强迫自己把递归版也手推三遍又在本地把三种解法全部跑通并打印每一步之后遇到任何链表反转变体我都不慌。这里也分享一个小技巧学链表题时不要只用眼睛看一定要动手打印。我见过许多人连printList都不会写就来刷链表题效率低很多。先把辅助函数准备好的习惯养成后面刷 K 个一组反转、回文链表时都不会吃亏。另外我也想说面试时如果一时紧张忘了代码不妨先从画图开始。把箭头一个个掰过去代码自然就顺着画出来了。这个动作我已经重复无数遍每次仍然管用。反转链表这道题说难不难说容易也不容易。真正把它吃透的标准不是“能复制答案”而是“指针在每一轮循环里指向谁、下一步怎么走、为什么不会丢节点”都能脱口而出。做到这一点之后你会发现不只是这道题整个链表分类的题目思路都通了不少。