剑指Offer 06题“从尾到头打印链表”应该算是最适合拿来当链表入门的第一道题题目本身不难但用C语言来写时栈怎么模拟、递归的代价在哪、返回数组和直接打印有什么区别这些点够你研究一阵子了。很多人在LeetCode、牛客或者面试现场碰到这道题第一反应是“这不就是遍历一遍再倒过来输出吗”。实际上这里面藏了几个关键选择能不能修改原链表、空间复杂度能不能接受O(n)、链表特别长的时候会不会栈溢出。这些都是面试官特别爱追问的点。这篇文章我会把三种主流解法都写一遍分别是辅助栈、递归、反转链表每种都给出可直接编译的C语言代码把边界条件、内存分配、复杂度这些坑都拆开讲清楚。适合刚准备刷题的C语言新手也适合想在面试前把这道题吃透、应付追问的老手。1. 题目拆解从尾到头打印到底在考什么1.1 题面分析与真实考点先看题面描述输入一个单链表的头节点要求从尾到头依次输出每个节点的值。这里的“从尾到头”是核心约束但真正考的是三件事。第一你知不知道链表是单向的。单向链表只能从头往后走不能从后往前退所以“倒序输出”这个需求天生就需要借助额外手段。第二你熟不熟悉常见的数据结构。栈的先进后出特性天然适合这种“逆序”场景递归本质上也是利用了系统调用栈。第三你会不会分析不同方案的代价。同样是能完成逆序输出三种做法的时间复杂度都是O(n)但空间复杂度分别是O(n)、O(n)、O(1)而且有的方案会破坏原链表结构有的不会。C语言跟刷题常用的语言还有一点不同没有现成的栈和队列容器一切都得自己用数组或者动态内存来模拟。很多人把Java版答案背得很熟换到C语言一写就卡在“栈怎么实现”上这就是本题用C语言写的真实门槛。另外要提醒一下不同平台对这道题的描述有一点点差异。原书版题目是“从尾到头打印链表”直接输出结果就行LeetCode版则是要求返回一个逆序后的int数组同时通过returnSize返回数组长度。我这篇文章两种实现都会覆盖注释里也会区分清楚。1.2 三条解题路线的选择标准先给一个总览方便你心里有数。下面这个表格可以帮你快速判断不同场景该选哪种做法。解法时间复杂度空间复杂度是否修改原链表适用场景辅助栈/数组O(n)O(n)否面试首选思路清晰不破坏原数据递归O(n)O(n)否代码最短但链表长时可能栈溢出反转链表O(n)O(1)是追问空间O(1)解法时使用或题目明确允许修改选哪种主要取决于面试官的约束条件。如果没说能不能改链表优先用辅助栈因为不会产生“把人家输入数据改了”的副作用。如果题目要求只能用O(1)额外空间那反转链表是标准答案。如果节点数量很少、题目又只有纯打印需求递归三行搞定也完全没问题。很多人的误区是一上来就写反转链表然后被追问“如果这个链表之后还要用怎么办”就愣住。所以下面的章节会按复杂度递增的顺序来讲把每种解法的适用边界说得明明白白。2. 解法一辅助栈数组模拟最稳的通用方案2.1 为什么第一个想到栈如果把链表从头到尾的访问顺序记为“正序”我们要输出的顺序恰好是它的反序。栈的特点是先进后出也就是你按顺序把1、2、3压进去弹出来的时候一定是3、2、1。这不就是“从尾到头”吗。所以在C语言里最直观的思路就是先遍历一遍链表把每个节点的值压入栈遍历结束后依次弹出栈顶元素并输出。整个过程不修改原链表输入数据完好无损。C语言没有标准库帮你管理一个“栈”但完全可以用数组模拟。数组的尾部就是栈顶入栈就是往数组末尾写数据出栈就是把数组下标往前退一格。关键是要预先知道数组多大所以需要先数一遍链表的节点总数这也是一次完整遍历。整体时间O(n)空间O(n)。2.2 返回数组版本数节点倒序填充在LeetCode这种需要返回数组的场景下辅助栈还有另一种更省事的写法数出节点总数然后申请同样大小的数组再从数组末尾往前填充链表值。#include stdio.h #include stdlib.h typedef struct ListNode { int val; struct ListNode *next; } ListNode; int* reversePrint(struct ListNode* head, int* returnSize) { int cnt 0; struct ListNode* p head; while (p ! NULL) { cnt; p p-next; } *returnSize cnt; if (cnt 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * cnt); p head; for (int i cnt - 1; i 0; i--) { ans[i] p-val; p p-next; } return ans; }这一段代码里有几个细节值得讲。第一为什么要先遍历一次求cnt。因为malloc分配数组必须指定大小链表又不像数组那样有len属性只能自己数。第二为什么从数组末尾往前填。第一次遍历正序得到的是1、2、3我们想让数组里存成3、2、1那么链表第一个节点值就应该落在数组最后一个位置以此类推。第三空链表必须单独处理。直接malloc(0)的行为在C标准里是实现定义的不同平台表现不一样与其赌这个不如显式返回NULL同时把*returnSize置0。面试时主动提到这一点是加分项。2.3 仅打印版本显式栈实现如果题目只需要打印不要求返回数组可以用一个等长的数组模拟栈先压栈再出栈输出。逻辑更贴近“栈”这个数据结构的本意。void reversePrintWithStack(struct ListNode* head) { int cnt 0; struct ListNode* p head; while (p ! NULL) { cnt; p p-next; } if (cnt 0) { return; } int* stack (int*)malloc(sizeof(int) * cnt); int top 0; p head; while (p ! NULL) { stack[top] p-val; p p-next; } while (top 0) { printf(%d , stack[--top]); } printf(\n); free(stack); }这里的top初始为0表示栈为空。每入栈一个值top加1。出栈时先top减1再访问stack[top]正好对应“先进后出”的顺序。这种写法相当于自己维护了一个栈指针理解了它后面看递归版本会顺畅很多。需要注意打印的格式问题。最后的值后面要不要留空格输出要不要换行这类细节在笔试平台经常成为“格式错误”的原因。我的习惯是先用printf()验证格式提交前再按题目要求调整。2.4 空间的细节与内存分配陷阱辅助栈法的空间复杂度是O(n)这在刷题里通常是可以接受的。但有几个内存相关的坑我见过不少人在上面翻车。第一个坑是malloc之后忘记free。刷题网站不一定检测内存泄漏但如果是你自己写测试程序跑反复申请不释放内存占用会一直涨。尤其是链表本身还要继续使用的时候栈数组、结果数组都该在输出完成后释放。第二个坑是malloc可能失败。在嵌入式或者内存受限环境里malloc返回NULL的情况真实存在。严谨的写法是申请后立刻判断直接return或做错误处理。第三个坑是返回数组在函数结束后被调用方free。很多C语言学习者不习惯这种方式以为局部数组返回后就没用了。这里用的malloc数组是堆内存函数返回后依然有效调用方负责释放就行。如果用了栈上的局部数组函数一返回就失效那是绝对要避免的。辅助栈法适合作为面试的第一版回答代码好写、思路好讲而且不会改坏原链表。接下来看看代码更短、但暗藏风险的递归解法。3. 解法二递归三行代码背后的代价3.1 递归的天然逆序特性递归解法的核心逻辑非常短要打印以head为头的链表可以先打印head-next这个子链表再打印head的值。一直递推下去最内层一定是最末尾的节点回溯时逐层打印自然就实现了从尾到头。这个思路依赖的是函数调用栈每一次递归都是一次压栈最深的那次调用对应链表的最后一个节点返回时是逐层弹出的过程。所以递归本质上是“隐式地用了栈”代码里却不用写任何栈操作。理解了这个点你就明白为什么递归能逆序也明白它跟显式栈其实是同一套思路的两种表达。区别只在空间开销和限制条件上。3.2 打印版与返回数组版实现纯打印版的递归实现代码只有几行。void reversePrintRecursive(struct ListNode* head) { if (head NULL) { return; } reversePrintRecursive(head-next); printf(%d , head-val); }第一次读这段代码的人可能会疑惑为什么先递归、再打印不应该是先打印再递归吗。这里的关键就是回溯顺序。以链表1-2-3为例调用过程是这样的第一层调用head1不满足空节点条件进入第二层调用head2再进入第三层调用head3第四层调用headNULL直接返回。返回后第三层打印3返回后第二层打印2返回后第一层打印1。最终输出3 2 1。如果要用递归返回逆序数组就不能光打印了。思路是先用递归求链表长度再递归填充数组。int getLength(struct ListNode* head) { if (head NULL) { return 0; } return 1 getLength(head-next); } void reverseFill(struct ListNode* head, int* ans, int* index) { if (head NULL) { return; } reverseFill(head-next, ans, index); ans[*index] head-val; (*index); } int* reversePrintRecursiveReturn(struct ListNode* head, int* returnSize) { int len getLength(head); *returnSize len; if (len 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * len); int index 0; reverseFill(head, ans, index); return ans; }注意reverseFill里index必须用指针。因为每次回溯到当前节点时index已经在子链表里被改过了如果用普通int传值数组填充位置会一直停在0导致每次都在覆盖第一个元素。3.3 递归深度的工程教训递归版本代码最短但真正的工程隐患在于链表深度。假设链表有10万个节点那递归深度就是10万层。C语言的调用栈通常不大在默认栈空间只有几兆的情况下10万层深度很可能直接把栈写爆程序直接崩溃。这在刷题时可能测试数据没那么极端但在真实开发中是实实在在的风险。我在调试一些链表操作代码时就碰到过本地小数据跑得好好的换了一个很长的数据集程序莫名退出加日志才发现是递归层数太多。所以我现在做题时会给自己一个默认规则题目没有明确说链表很短就不要把递归当首选。如果非要用递归先确认数据规模。这个规则在面试里说出来面试官会觉得你考虑过生产环境不是只会背题。辅助栈和递归都是空间O(n)。如果面试官追加一句“能不能用O(1)空间”就要请出反转链表法了。4. 解法三反转链表O(1)空间的硬核方案4.1 迭代反转的三个指针逻辑反转链表是链表题里另一道经典思路是遍历时不断把当前节点的next指向前一个节点。需要维护三个指针prev、cur、next。prev记录当前节点的前一个节点初始为NULL。cur是当前正在处理的节点初始为链表头。next临时保存cur-next防止修改完cur-next后丢失后续节点。每一步做的事情是先把next保存下来然后把cur-next指向prev接着把prev更新为cur最后把cur更新为next。遍历结束后prev就是新的链表头。C语言实现如下。struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! NULL) { struct ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; }这段代码只看一两次容易绕建议自己拿一张纸画一遍。画的时候重点观察每轮循环结束后prev和cur分别指向谁。我第一次学的时候就是因为没画图总觉得cur-next指向prev之后就把链表弄断了其实next已经提前保存了后面的节点不会断。4.2 反转后打印的完整流程反转链表后原来的尾节点变成了新链表头原来的头节点变成了新链表尾。此时从新链表头顺序遍历打印得到的就是原链表的倒序。完整流程如下。void reversePrintByReverseList(struct ListNode* head) { struct ListNode* newHead reverseList(head); struct ListNode* p newHead; while (p ! NULL) { printf(%d , p-val); p p-next; } printf(\n); }如果只是单纯为了打印到这里就结束了。但如果题目希望保持链表原状或者调用方后续还要用原始链表这里就需要再反转一次恢复。恢复的原理和第一次反转完全一样直接再调用一次reverseList(newHead)就行。如果要返回逆序数组同样可以反转后遍历填充。下面这段代码综合了反转、填充、恢复三个动作面试时如果能在白板上写出这个版本会显得思路非常完整。int* reversePrintWithReverseList(struct ListNode* head, int* returnSize) { int cnt 0; struct ListNode* p head; while (p ! NULL) { cnt; p p-next; } *returnSize cnt; if (cnt 0) { return NULL; } struct ListNode* newHead reverseList(head); int* ans (int*)malloc(sizeof(int) * cnt); p newHead; for (int i 0; i cnt; i) { ans[i] p-val; p p-next; } // 如果需要保持原链表结构反转回来 reverseList(newHead); return ans; }这里注意最后一步reverseList(newHead)会把链表重新变成原来的顺序因为newHead是反转后的头对它再反转一次正好恢复原状。代价是额外一次O(n)遍历时间复杂度依然是O(n)常数变大了而已。4.3 修改原链表的影响评估反转链表最大的特点就是额外空间O(1)这是它对比前两种方案的核心优势。但它会临时破坏链表原有的链接关系这是它的致命伤。在面试中如果要选这个方案必须主动说明“我会修改原链表如果题目不允许我会在输出后反转恢复。”这句话说出来效果比闷头写完全部代码要好得多。还有一个现实问题是节点里的数据如果非常大拷贝处理不划算如果链表节点非常多递归又容易爆栈。这种情况下反转链表法反而成了最合适的方案。毕竟只需要三个指针变量空间恒定。工程里处理长链表倒序输出时如果允许短暂的临时结构变化反转法值得优先考虑。这三种解法的完整代码拼起来其实就可以组成一个可以编译运行、覆盖多种边界情况的测试程序了。下面这部分我直接给你一个能跑的最小测试框架方便你复制到自己机器上验证。5. 可直接编译的完整测试代码5.1 链表构建与内存回收刷题时链表头节点都是题目给好的但本地测试必须自己建链表。我习惯写一个从数组构建链表的工具函数顺便写一个释放链表的函数。这两个函数在所有链表题目里都能复用。#include stdio.h #include stdlib.h typedef struct ListNode { int val; struct ListNode *next; } ListNode; ListNode* buildList(int* nums, int size) { if (size 0) { return NULL; } ListNode* head (ListNode*)malloc(sizeof(ListNode)); head-val nums[0]; head-next NULL; ListNode* tail head; for (int i 1; i size; i) { ListNode* node (ListNode*)malloc(sizeof(ListNode)); node-val nums[i]; node-next NULL; tail-next node; tail node; } return head; } void freeList(ListNode* head) { while (head ! NULL) { ListNode* temp head; head head-next; free(temp); } }构建链表的逻辑很简单核心是维护一个tail指针每次新建节点挂到tail后面然后更新tail。释放链表时要注意先用temp保存当前节点再把head往后移动否则先free再取head-next就是访问已经释放的内存属于未定义行为。5.2 三种解法的测试框架与运行结果我把前面几种解法放到一个程序里测试main函数里分别跑三个场景多节点链表、单节点链表、空链表。下面的代码可以直接复制编译。// 解法一数节点倒序填充 int* reversePrint(struct ListNode* head, int* returnSize) { int cnt 0; struct ListNode* p head; while (p ! NULL) { cnt; p p-next; } *returnSize cnt; if (cnt 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * cnt); p head; for (int i cnt - 1; i 0; i--) { ans[i] p-val; p p-next; } return ans; } // 解法二递归填充 int getLength(struct ListNode* head) { if (head NULL) { return 0; } return 1 getLength(head-next); } void reverseFill(struct ListNode* head, int* ans, int* index) { if (head NULL) { return; } reverseFill(head-next, ans, index); ans[*index] head-val; (*index); } int* reversePrintRecursiveReturn(struct ListNode* head, int* returnSize) { int len getLength(head); *returnSize len; if (len 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * len); int index 0; reverseFill(head, ans, index); return ans; } // 解法三反转链表返回数组 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! NULL) { struct ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; } int* reversePrintWithReverseList(struct ListNode* head, int* returnSize) { int cnt 0; struct ListNode* p head; while (p ! NULL) { cnt; p p-next; } *returnSize cnt; if (cnt 0) { return NULL; } struct ListNode* newHead reverseList(head); int* ans (int*)malloc(sizeof(int) * cnt); p newHead; for (int i 0; i cnt; i) { ans[i] p-val; p p-next; } // 恢复原链表顺序 reverseList(newHead); return ans; } void printArray(int* nums, int size) { if (size 0) { printf([]\n); return; } printf([); for (int i 0; i size; i) { printf(%d, nums[i]); if (i size - 1) { printf(, ); } } printf(]\n); } int main() { int nums1[] {2, 4, 6, 8, 10}; int nums2[] {7}; int size1 (int)(sizeof(nums1) / sizeof(nums1[0])); int size2 (int)(sizeof(nums2) / sizeof(nums2[0])); ListNode* list1 buildList(nums1, size1); ListNode* list2 buildList(nums2, size2); ListNode* list3 NULL; int returnSize 0; printf(解法一倒序填充\n); int* ans reversePrint(list1, returnSize); printArray(ans, returnSize); free(ans); printf(解法二递归\n); ans reversePrintRecursiveReturn(list1, returnSize); printArray(ans, returnSize); free(ans); printf(解法三反转链表\n); ans reversePrintWithReverseList(list1, returnSize); printArray(ans, returnSize); free(ans); printf(单节点测试\n); ans reversePrint(list2, returnSize); printArray(ans, returnSize); free(ans); printf(空链表测试\n); ans reversePrint(list3, returnSize); printArray(ans, returnSize); free(ans); freeList(list1); freeList(list2); return 0; }运行后主输出是解法一倒序填充 [10, 8, 6, 4, 2] 解法二递归 [10, 8, 6, 4, 2] 解法三反转链表 [10, 8, 6, 4, 2] 单节点测试 [7] 空链表测试 []三种解法输出一致说明实现都没有明显逻辑问题。注意解法三在填充完数组后我又做了一次reverseList(newHead)所以list1的顺序被恢复后续测试和freeList都不会受反转影响。这个设计是我故意加的你可以试着注释掉那行恢复代码看看后续输出会不会出问题这是一个很直观体会“修改原链表副作用”的实验。5.3 链表构建与测试时的日常注意点本地测试链表代码最烦的问题就是内存。我写测试时会特别注意两点一是每次malloc都要有对应的free二是释放链表后把指针置为NULL防止后面误用。另外测试用例不能只测题目给的正常数据。空链表和单节点链表是最容易漏掉的边界很多线上编译器报错恰恰是这两种情况。建议建一个固定模板一个多节点、一个单节点、一个空链表每次写完链表题都先跑这三个用例。这样养成习惯之后很多低级错误能提前暴露。这三个用例跑完三种解法都能正常工作接下来要解决的就是面试追问环节里那些“看起来很简单、答不上来就很尴尬”的问题。6. 常见问题与排查技巧实录6.1 空链表和单节点边界的处理空链表在三种解法里都要单独考虑。辅助栈法里链表为空时cnt等于0如果直接malloc(0)在Windows上可能返回NULL在Linux上可能返回一个非NULL但不可用的指针行为不统一。所以必须提前判断cnt0直接返回NULL并把returnSize设为0。单节点链表相对简单不管哪种解法逆序结果都是它自己。递归版本里head-next是NULL递归一层立即返回回溯时打印head-val逻辑天然正确。反转链表法里只有一次循环prev变成原来的head输出也没有问题。但单节点链表有个容易踩的坑打印数组时如果代码里在数字后多加逗号或者少加换行评测系统会判格式错误。我建议在printArray之类的基础工具函数里提前把这些情况封装好做题时就不用每次重新写。6.2 malloc失败与空指针判断C语言刷题最容易被人忽略的就是malloc返回值检查。在很多在线评测平台上内存充足不检查也能过。但在真实环境或面试官追问时不检查就是短板。写malloc之后立刻判断是比较规范的做法比如int* ans (int*)malloc(sizeof(int) * cnt); if (ans NULL) { *returnSize 0; return NULL; }这里还有一个细节要注意malloc的入参最好是sizeof(int) * cnt不要直接写4 * cnt。虽然int在很多平台上占4字节但保险起见用sizeof一是可读性好二是在不同编译器、不同平台上更不容易出错。6.3 面试高频追问与标准回答这道题面试官特别喜欢追加问题我整理几个常见追问和答题要点你可以对照自测。追问一能不能用O(1)额外空间做答可以用反转链表法。遍历一次把链表反转顺序遍历输出不用额外数组和递归栈只需要三个指针。代价是原链表结构被临时修改如果后续不能用原链表输出后再反转恢复。追问二递归为什么空间复杂度是O(n)答因为递归深度等于链表长度每一层调用都要占用系统调用栈空间。虽然代码里没有显式分配数组但函数调用栈本身就是额外空间。隐蔽在这里很多人误以为递归是O(1)空间。追问三链表很长递归会怎样答会栈溢出。C语言默认栈空间有限深度达到几万层就可能崩溃。解决方案是用显式栈或者反转链表把空间开销控制在可控范围。追问四三种解法分别适合什么场景答默认不修改原链表、空间O(n)可接受用辅助栈或者递归代码简洁优先、数据规模小用递归额外空间严格受限用反转链表如果题目要求输出后原链表还能用反转后记得恢复。追问五换成本地测试链表怎么建这道题给的是单链表所以建链时要注意尾插法。我见过有人把数组建链写成头插法结果是输入顺序和链表顺序正好反过来逆序输出反而变成正序跑半天找不到原因。测试工具函数建议大家专门保存一份以后所有链表题都能复用。6.4 独家避坑心得刷这道题连着写三遍印象最深的是“输出前确认链表状态”这一件事。尤其是反转链表法如果在函数里既不恢复原链表、调用方又不知情后续操作很容易出现诡异bug。最好的习惯是每个函数注释里都写清楚“是否修改原链表”谁调用谁负责维护。调试链表题还有一个实用技巧定义一个极简打印函数先打印当前链表所有节点用来确认输入和中间状态。怀疑哪里出问题就在关键步骤前后打印一遍。很多链表题不是思路错而是指针改来改去之后指向错了靠纸笔推演不如直接打印直观。最后再分享一个小经验这道题如果你把三种解法都完整写一遍并且能在白板上解释清楚各自的复杂度和副作用再去面对任何链表的逆序、反转类题目底子就相当扎实了。面试碰到变体题比如“逆序删除节点”“逆序相加”也能很快迁移思路。