1. 题目到底在考什么单链表不能回头打印顺序被压成了栈剑指 Offer 06. 从尾到头打印链表C语言题号很靠前看起来人畜无害但它在所有链表题里属于“第一道分水岭”。很多人背得下来链表插入删除一看到这道题反而卡住原因不是不会写而是没想清楚一个问题单链表只能从head往后走凭什么要我先输出链尾的值题目本身很短输入一个链表的头节点从尾到头反过来返回每个节点的值返回值放在一个数组里。比如链表值是1、3、2你要返回一个长度为3的数组顺序是2、3、1。限制条件是链表长度0到10000这个范围决定了某些解法能不能用。我刚入行那会儿第一反应是把数组倒过来不就行了先正序遍历一遍链表把所有节点值存进数组然后把这个数组从后往前拷贝到答案数组里。这个思路本身没有错但它只回答了“怎么做”没回答“为什么是这样”。面试官真正想听的是后面那句从尾到头本质上是先遇到的节点最后输出后遇到的节点最先输出这不就是先进后出的栈吗拿日常场景类比就像一摞盘子你先放的盘子在最底下最后才能拿到你最后放的盘子在最上面伸手就能取。链表的遍历顺序是从头到尾而输出顺序是从尾到头中间恰好差了一个“后进先出”的转换。这个转换就是栈。而且这里还要意识到一个反直觉的点链表节点里只存了向后的指针根本没有向前指针所以你无法直接从最后一个节点回头。即使你想到可以先走到链表末尾也得走回头路才能拿倒数第二个节点。每拿一个节点都从头走一遍总复杂度就是O(n²)10000个节点时已经能明显感觉到慢。这个方案不是不行但连自己这关都过不去。这道题对用C语言刷题的人还有一个额外门槛C语言的标准库里没有现成的栈容器。Java有StackC有std::stackPython里一个list就能模拟而C语言只能靠数组、链表或者函数调用栈自己造轮子。所以这道题不仅是考链表还顺带考了你“用C语言实现一个栈”的基本功。下一节我会把候选方案全部摆出来先做取舍再给出能直接复制到判题系统里的C语言代码。2. 三套候选方案先做取舍数组栈、递归栈、反转链表先说结论这道题的可行方案很多我给大家梳理三条主线它们分别对应三种不同的程序员思维。2.1 方案A辅助数组模拟栈最稳的保底答案第一种做法是开一个和链表长度一样的数组用它模拟栈。先遍历链表统计节点个数然后申请一块同样大小的内存作为输出数组。接着再遍历链表这次从数组最后一个位置开始往前填值。这个方案的优点是代码直白、空间可控、不修改原来的链表结构判题系统怎么测都不会出幺蛾子。缺点是需要预知链表长度所以必须先遍历一次链表统计个数。也就是说总共要遍历两次链表虽然时间复杂度还是O(n)但常数项略大。2.2 方案B递归输出用函数调用栈当隐式栈第二种做法是递归。递归函数有一个天然特性先调用后返回。你把“输出当前节点值”这个动作放在递归调用之后那么内层函数会先执行完外层函数才会执行输出从效果上看就是先处理链尾、再处理链头。代码会非常短三五行就能写完而且思维上很优雅。但这里有个必须警惕的坑链表的长度上限是10000递归深度为10000时C语言默认的函数调用栈通常扛不住。在常见的Linux环境默认栈大小8MB、Windows默认1MB的情况下10000层递归大概率会栈溢出程序直接崩溃。递归方案适合在面试中展示思路但真要放到判题系统里跑长链表风险不小。2.3 方案C反转链表再顺序输出空间最省但动了原链表第三种做法是先把链表反转让原来的尾节点变成头节点然后从头到尾顺序遍历得到的节点值序列自然就是从尾到头的顺序。这个方法空间复杂度可以做到O(1)不需要辅助数组缺点非常明显它修改了传入的链表结构。在在线评测系统里这道题通常没有禁止你改结构但面试时一定要先问清楚“允不允许修改原链表”。如果面试官允许修改链表结构方案C其实是最能体现链表基本功的解法。反转链表本身就是高频考点一举两得。如果面试官说“不能动原链表”那就老老实实退回方案A或方案B。三套方案从空间、时间、对原链表的影响三个维度对比如下方案时间复杂度空间复杂度是否修改原链表适合场景辅助数组模拟栈O(n)O(n)否日常写法、在线评测最稳递归隐式栈O(n)O(n)调用栈否展示思路短链表可用反转链表O(n)O(1)是允许改结构、要求省空间时我个人建议初学阶段先把方案A吃透因为它最不容易写错再理解方案B的递归时机这是思维的提升方案C放到你已经能把前三者写得很熟练之后再去练因为它牵扯到指针修改顺序是三个方案里最容易写出野指针的。3. 三套方案的C语言实现与细节打磨这三个方案我都用C语言完整实现了并且是针对判题系统的接口格式写的。判题系统一般会要求你实现这样一个函数int* reversePrint(struct ListNode* head, int* returnSize);含义是传入链表头指针返回一个动态申请的数组数组长度通过returnSize这个指针带出去。返回值就是数组首地址。注意这个returnSize很多新手会漏写一旦漏了判题系统读到的数组长度就是随机值轻则越界重则直接判错。3.1 方案A实现两次遍历 反向填充数组先看完整代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int* reversePrint(struct ListNode* head, int* returnSize) { // 第一次遍历统计链表的节点个数 int count 0; struct ListNode* p head; while (p ! NULL) { count; p p-next; } *returnSize count; // 空链表直接返回NULL if (count 0) { return NULL; } // 申请存储结果的数组 int* ans (int*)malloc(sizeof(int) * count); if (ans NULL) { // malloc失败时返回NULL避免后续写出野指针 return NULL; } // 第二次遍历从数组最后一个位置开始倒着填 p head; int index count - 1; while (p ! NULL) { ans[index] p-val; index--; p p-next; } return ans; }这里有一个非常关键的设计第二次遍历链表时我没有先把正序结果存下来再手动反转数组而是直接让指针从头开始走下标从数组末尾开始递减。你可以自己算一下链表第一个节点的值最后应该出现在数组的最后一个位置链表最后一个节点的值应该出现在数组的第一个位置。所以第一次遍历时p先指向头节点index指向count - 1头节点的值填入末尾然后p往后走index往前移刚好一一对应。这种做法省掉了单独反转数组的代码也降低了出错的概率。还有一个边界问题是空链表。如果count 0函数直接return NULL同时把*returnSize置为0。有些判题系统的标准答案在空链表时要求返回非NULL的指针但绝大多数系统接受NULL因为长度是0根本不会去读这个数组。真正需要注意的是malloc(0)这种写法C标准规定它的行为是实现定义的有的编译器会返回一个非NULL的指针但你不能拿它当正常数组用。所以干脆自己提前拦下空链表不要依赖malloc(0)的行为。3.2 方案B实现递归的“递去”与“归来”各干一件事递归方案我写成两个函数外层函数负责申请数组和统计长度内层递归函数负责把链表节点值填入正确位置。int fillAnsFromList(int* ans, struct ListNode* node, int idx) { if (node NULL) { return idx; } idx fillAnsFromList(ans, node-next, idx); ans[idx] node-val; return idx 1; } int* reversePrint(struct ListNode* head, int* returnSize) { int count 0; struct ListNode* p head; while (p ! NULL) { count; p p-next; } *returnSize count; if (count 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * count); if (ans NULL) { return NULL; } fillAnsFromList(ans, head, 0); return ans; }理解这段代码的关键在递归函数fillAnsFromList。它先一路递归下去一直到node NULL才停止然后逐层返回。返回的过程中每一层执行ans[idx] node-val;并且把idx加1返回给上一层。举个例子假设链表是1 - 2 - 3第一次调用fillAnsFromList(ans, 1号节点, 0)因为1号节点不为空继续调用fillAnsFromList(ans, 2号节点, 0)继续调用fillAnsFromList(ans, 3号节点, 0)继续调用fillAnsFromList(ans, NULL, 0)直接返回0回到3号节点这一层idx 0执行ans[0] 3返回1回到2号节点这一层idx 1执行ans[1] 2返回2回到1号节点这一层idx 2执行ans[2] 1返回3。最终数组是[3, 2, 1]完美符合从尾到头的要求。递归方案里最容易被忽略的点是为什么“先递归、后赋值”就能反过来因为递归调用这里天然是一个栈内层的调用一定比外层先返回。后返回的外层函数反而先把值写进了数组的靠后位置。你要是把赋值放到递归调用之前那输出的就是正序了。这个“放前放后”的差别就是递归的精髓。但我要再次强调递归深度的隐患是真实存在的。题目限制链表长度0到1000010000层递归在所有常见操作系统上都很危险。某开发者朋友有一次在自己在VSCode里跑通了一万节点的测试但换到另一个默认栈更小的环境就崩了排查了半天才发现是递归爆栈。所以这个方案我更推荐用来理解原理不是推荐你作为第一解法。3.3 方案C实现反转链表后顺序遍历空间O(1)反转链表的迭代法也是一个经典模板这里直接给出实现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* reversePrint(struct ListNode* head, int* returnSize) { struct ListNode* newHead reverseList(head); // 先统计反转后的节点个数 int count 0; struct ListNode* p newHead; while (p ! NULL) { count; p p-next; } *returnSize count; if (count 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * count); if (ans NULL) { return NULL; } // 反转后的链表顺序就是原来的从尾到头 p newHead; int index 0; while (p ! NULL) { ans[index] p-val; p p-next; } return ans; }反转的核心逻辑在reverseList函数里用prev保存前一个节点cur保存当前节点next保存下一个节点。每次把cur-next指向prev然后整体往后移动。这个“先备份下一个节点再改当前指针”的顺序是绝对不能乱的。你把next的备份放到修改cur-next之后那cur-next已经变了就找不到原来的下一个节点了。这段代码里第一个要注意的问题是head指针在反转后已经没有意义了因为原来的头节点变成了新链表的尾节点它的next指向NULL。所以后续遍历必须从newHead开始。第二个问题是反转操作改变了原链表结构。如果整个程序之后还要用原来的链表做别的操作那就有问题了。我在模拟面试时试过有位面试官明确说“不能修改链表结构”当时如果我选了方案C就得把整个思路推翻。所以用这个方案前一定要先确认题目要求和面试官的意图。4. 边界测试与C语言内存误区这些坑我全踩过写代码是一回事能扛住裁判系统的各种边界输入又是另一回事。下面我把这次折腾中遇到的所有边界和内存问题整理出来这几条是真正能帮你省时间的经验。4.1 边界用例清单不要只测长度为3的链表我刷题时习惯建一张自测表每道题至少跑通下面这些情况测试场景输入链表期望输出最容易出问题的地方空链表NULL空数组malloc(0)行为不确定要提前拦截单节点链表[5][5]数组下标是否越界递增序列[1,2,3,4,5][5,4,3,2,1]反转数组下标的计算重复值[7,7,7][7,7,7]无法通过值判断顺序对不对容易漏测长链表10000个节点逆序序列递归方案是否爆栈超大节点值[2147483647,-2147483648]逆序int类型是否能存下空链表和单节点是最容易翻车的。空链表时如果你没有在count 0时提前返回而是执行了malloc(0)再返回指针虽然一部分编译器允许但行为不可移植。我建议任何平台都统一写成return NULL。单节点链表则要验证index count - 1 0的逻辑也就是第一次填充就落在数组下标0上循环结束后index变成-1。这个看不出问题但如果你把while写成了do...while单节点时数组下标会先访问ans[-1]直接越界。很多编译器不会提醒你只有跑起来才知道错。重复值的测试很多人会跳过觉得“值一样测了也没意义”。其实恰恰相反正是因为值一样你才能通过打印每个位置的下标来验证顺序到底有没有写反。我踩过的一个真实教训是数组正序填好然后手动反转时多写了一次循环导致整个数组被翻了两遍输出和正序完全一样。如果测试用例里没有重复值这个错误很容易被误判成“正常”。4.2 C语言特有的内存误区returnSize、malloc失败、野指针returnSize忘记赋值是新手最高发的错误。判题系统拿到指针后会往这个地址读出数组长度。你不赋值它读到的可能是上一块内存残留的垃圾值结果就是数组越界访问。正确做法是在函数最开始就处理先统计完节点个数立刻把count写进*returnSize之后再开始申请内存。malloc返回值检查也不能省。很多人觉得刷题嘛malloc失败概率几乎是零所以随手就忽略。但C语言的面试题里评委经常故意追问“如果malloc返回NULL怎么办”。你代码里写了判空面试官会认可你的严谨没写他可能觉得你对C语言内存管理还没建立完整意识。所以两份代码里我都加了if (ans NULL)的分支这是给自己上的一层保险。还有一个细节在判题系统里你malloc出来的数组系统会自动帮你释放所以不需要free。但如果你在本地写测试程序那一定记得在打印完结果后free(ans)。我见过有人把判题系统里的代码原封不动搬到本地跑完又不释放内存一个测试函数循环100次内存涨了几十MB。这虽然不影响判题但作为C程序员随手释放自己申请的堆内存是基本素养。4.3 验证代码正确性的一个小技巧把链表画在三张纸上调试链表题时我个人的习惯是只在脑子里推演容易出错必须画图。具体做法是在纸上画出三个节点每个节点画两个格子一个放val一个放next指针。然后把代码里每一行操作对应的指针变化画出来。比如反转链表时prev、cur、next三个指针怎么移动画三遍基本全明白了。这个方法对检查递归也有效。递归难的不是逻辑而是你脑中要同时维护一条“递去”的线和一条“归来”的线。两件事混在一起就容易乱。画图时我把递去的路径用实线标归来的路径用虚线标赋值发生在虚线上就永远不会搞反。5. 面试追问题目一变你选哪种解法马上要换光会写原题还不够面试官几乎一定会换条件追问这才是真正拉开差距的地方。我总结过三种最常见的变体每种对应完全不同的解法取向。5.1 变体一接口加了const禁止修改链表如果函数的头指针参数变成const struct ListNode* head方案C就直接出局了。const语义上明确告诉你不能改动节点哪怕只是把next扭转一下也不行。这种场景下你只剩下两个选择辅助数组模拟栈或者递归。考虑到递归有栈溢出风险面试时我会先说“用辅助数组模拟栈”然后主动补一句“当然也可以用递归但链表长度10000时递归有爆栈风险所以这里我更倾向显式栈”。这一句话能同时展示你对const语义的理解和对空间复杂度的敏感度比闷头写代码要加分得多。5.2 变体二要求空间O(1)不能开额外数组这是另一个极端不让你用辅助数组还要逆序输出。如果仍然不允许修改链表那这道题在数学上就没有O(1)空间的解法。因为单链表本身只支持单向遍历逆序访问又没有任何“回头”信息你至少要保存一路往回走的路径信息。保存这个信息就需要O(n)空间无论用数组还是调用栈。所以面试官如果这么问你直接回答“不修改链表的前提下理论上不可能做到O(1)空间”是正确思路这不是你不会写而是确实存在下界。如果允许修改链表反转法就是唯一正解。这时候你不需要malloc任何数组遍历反转后的链表时边遍历边输出空间就是常数级别。三种方案里只有它能做到。5.3 变体三K个一组逆序打印链表比如链表是1-2-3-4-5-6-7-8要求每3个一组组内逆序打印输出就是3、2、1、6、5、4、8、7。这个问题本质上已经升级成“K个一组反转链表”的变种。你可以先实现一个局部反转函数处理从某节点开始的连续K个节点翻转后从新头开始遍历输出再跳到下一组的起始位置。这种变体考的是你能否把一道简单题的核心思想复用到复杂场景。如果原题你能清晰说出“栈/递归/反转”三者的关系那么变体题你大概率也能想到组内逆序输出 组内反转组间保持原顺序。它的实现细节比原题复杂很多但战略方向是一致的。还有一个容易被问到的变体打印到文件而不是返回数组。那就是把printf(%d , node-val)换成写文件操作其他逻辑一模一样这里就不再赘述了。6. 我的最终选择与一个画图小技巧综合下来我自己在判题系统里最终提交的是方案A也就是两次遍历加反向填充数组。原因很简单它不依赖递归栈不修改输入链表也不需要考虑malloc(0)等不确定行为内存可控逻辑清晰在所有边界情况下都能稳定运行。刷题不是为了炫技稳定通过才是第一目标。但如果你让我给初学者一个学习路径我会建议先手写方案A直到闭着眼都能写对然后把方案B的递归调用顺序彻底搞明白最后用方案C反向加深对链表指针操作的理解。三套方案全部吃透之后你再看其他链表题会有一种“来来回回就那么几种招式”的通透感。最后再分享一个我在面试中验证过的答题习惯拿到链表题先别急着写代码拿起笔在纸上画三个节点的链表标清楚每一步指针的指向。画完再动手写代码出错率至少降低一半。有的开发者觉得画图浪费时间实际上写出一个带野指针的版本再去调试浪费的时间比画图多得多。这个习惯我保持了很多年每次写链表的原地操作都靠它兜底。这道题的核心简单说就是“先进后出”四个字。想通了这一层代码只是把它翻译成C语言而已。 
长河君 · 2026/10/20 3:28:55 · 阅读 1.2k 从尾到头打印链表：C语言实现栈、递归与反转链表三种解法
1. 题目到底在考什么单链表不能回头打印顺序被压成了栈剑指 Offer 06. 从尾到头打印链表C语言题号很靠前看起来人畜无害但它在所有链表题里属于“第一道分水岭”。很多人背得下来链表插入删除一看到这道题反而卡住原因不是不会写而是没想清楚一个问题单链表只能从head往后走凭什么要我先输出链尾的值题目本身很短输入一个链表的头节点从尾到头反过来返回每个节点的值返回值放在一个数组里。比如链表值是1、3、2你要返回一个长度为3的数组顺序是2、3、1。限制条件是链表长度0到10000这个范围决定了某些解法能不能用。我刚入行那会儿第一反应是把数组倒过来不就行了先正序遍历一遍链表把所有节点值存进数组然后把这个数组从后往前拷贝到答案数组里。这个思路本身没有错但它只回答了“怎么做”没回答“为什么是这样”。面试官真正想听的是后面那句从尾到头本质上是先遇到的节点最后输出后遇到的节点最先输出这不就是先进后出的栈吗拿日常场景类比就像一摞盘子你先放的盘子在最底下最后才能拿到你最后放的盘子在最上面伸手就能取。链表的遍历顺序是从头到尾而输出顺序是从尾到头中间恰好差了一个“后进先出”的转换。这个转换就是栈。而且这里还要意识到一个反直觉的点链表节点里只存了向后的指针根本没有向前指针所以你无法直接从最后一个节点回头。即使你想到可以先走到链表末尾也得走回头路才能拿倒数第二个节点。每拿一个节点都从头走一遍总复杂度就是O(n²)10000个节点时已经能明显感觉到慢。这个方案不是不行但连自己这关都过不去。这道题对用C语言刷题的人还有一个额外门槛C语言的标准库里没有现成的栈容器。Java有StackC有std::stackPython里一个list就能模拟而C语言只能靠数组、链表或者函数调用栈自己造轮子。所以这道题不仅是考链表还顺带考了你“用C语言实现一个栈”的基本功。下一节我会把候选方案全部摆出来先做取舍再给出能直接复制到判题系统里的C语言代码。2. 三套候选方案先做取舍数组栈、递归栈、反转链表先说结论这道题的可行方案很多我给大家梳理三条主线它们分别对应三种不同的程序员思维。2.1 方案A辅助数组模拟栈最稳的保底答案第一种做法是开一个和链表长度一样的数组用它模拟栈。先遍历链表统计节点个数然后申请一块同样大小的内存作为输出数组。接着再遍历链表这次从数组最后一个位置开始往前填值。这个方案的优点是代码直白、空间可控、不修改原来的链表结构判题系统怎么测都不会出幺蛾子。缺点是需要预知链表长度所以必须先遍历一次链表统计个数。也就是说总共要遍历两次链表虽然时间复杂度还是O(n)但常数项略大。2.2 方案B递归输出用函数调用栈当隐式栈第二种做法是递归。递归函数有一个天然特性先调用后返回。你把“输出当前节点值”这个动作放在递归调用之后那么内层函数会先执行完外层函数才会执行输出从效果上看就是先处理链尾、再处理链头。代码会非常短三五行就能写完而且思维上很优雅。但这里有个必须警惕的坑链表的长度上限是10000递归深度为10000时C语言默认的函数调用栈通常扛不住。在常见的Linux环境默认栈大小8MB、Windows默认1MB的情况下10000层递归大概率会栈溢出程序直接崩溃。递归方案适合在面试中展示思路但真要放到判题系统里跑长链表风险不小。2.3 方案C反转链表再顺序输出空间最省但动了原链表第三种做法是先把链表反转让原来的尾节点变成头节点然后从头到尾顺序遍历得到的节点值序列自然就是从尾到头的顺序。这个方法空间复杂度可以做到O(1)不需要辅助数组缺点非常明显它修改了传入的链表结构。在在线评测系统里这道题通常没有禁止你改结构但面试时一定要先问清楚“允不允许修改原链表”。如果面试官允许修改链表结构方案C其实是最能体现链表基本功的解法。反转链表本身就是高频考点一举两得。如果面试官说“不能动原链表”那就老老实实退回方案A或方案B。三套方案从空间、时间、对原链表的影响三个维度对比如下方案时间复杂度空间复杂度是否修改原链表适合场景辅助数组模拟栈O(n)O(n)否日常写法、在线评测最稳递归隐式栈O(n)O(n)调用栈否展示思路短链表可用反转链表O(n)O(1)是允许改结构、要求省空间时我个人建议初学阶段先把方案A吃透因为它最不容易写错再理解方案B的递归时机这是思维的提升方案C放到你已经能把前三者写得很熟练之后再去练因为它牵扯到指针修改顺序是三个方案里最容易写出野指针的。3. 三套方案的C语言实现与细节打磨这三个方案我都用C语言完整实现了并且是针对判题系统的接口格式写的。判题系统一般会要求你实现这样一个函数int* reversePrint(struct ListNode* head, int* returnSize);含义是传入链表头指针返回一个动态申请的数组数组长度通过returnSize这个指针带出去。返回值就是数组首地址。注意这个returnSize很多新手会漏写一旦漏了判题系统读到的数组长度就是随机值轻则越界重则直接判错。3.1 方案A实现两次遍历 反向填充数组先看完整代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int* reversePrint(struct ListNode* head, int* returnSize) { // 第一次遍历统计链表的节点个数 int count 0; struct ListNode* p head; while (p ! NULL) { count; p p-next; } *returnSize count; // 空链表直接返回NULL if (count 0) { return NULL; } // 申请存储结果的数组 int* ans (int*)malloc(sizeof(int) * count); if (ans NULL) { // malloc失败时返回NULL避免后续写出野指针 return NULL; } // 第二次遍历从数组最后一个位置开始倒着填 p head; int index count - 1; while (p ! NULL) { ans[index] p-val; index--; p p-next; } return ans; }这里有一个非常关键的设计第二次遍历链表时我没有先把正序结果存下来再手动反转数组而是直接让指针从头开始走下标从数组末尾开始递减。你可以自己算一下链表第一个节点的值最后应该出现在数组的最后一个位置链表最后一个节点的值应该出现在数组的第一个位置。所以第一次遍历时p先指向头节点index指向count - 1头节点的值填入末尾然后p往后走index往前移刚好一一对应。这种做法省掉了单独反转数组的代码也降低了出错的概率。还有一个边界问题是空链表。如果count 0函数直接return NULL同时把*returnSize置为0。有些判题系统的标准答案在空链表时要求返回非NULL的指针但绝大多数系统接受NULL因为长度是0根本不会去读这个数组。真正需要注意的是malloc(0)这种写法C标准规定它的行为是实现定义的有的编译器会返回一个非NULL的指针但你不能拿它当正常数组用。所以干脆自己提前拦下空链表不要依赖malloc(0)的行为。3.2 方案B实现递归的“递去”与“归来”各干一件事递归方案我写成两个函数外层函数负责申请数组和统计长度内层递归函数负责把链表节点值填入正确位置。int fillAnsFromList(int* ans, struct ListNode* node, int idx) { if (node NULL) { return idx; } idx fillAnsFromList(ans, node-next, idx); ans[idx] node-val; return idx 1; } int* reversePrint(struct ListNode* head, int* returnSize) { int count 0; struct ListNode* p head; while (p ! NULL) { count; p p-next; } *returnSize count; if (count 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * count); if (ans NULL) { return NULL; } fillAnsFromList(ans, head, 0); return ans; }理解这段代码的关键在递归函数fillAnsFromList。它先一路递归下去一直到node NULL才停止然后逐层返回。返回的过程中每一层执行ans[idx] node-val;并且把idx加1返回给上一层。举个例子假设链表是1 - 2 - 3第一次调用fillAnsFromList(ans, 1号节点, 0)因为1号节点不为空继续调用fillAnsFromList(ans, 2号节点, 0)继续调用fillAnsFromList(ans, 3号节点, 0)继续调用fillAnsFromList(ans, NULL, 0)直接返回0回到3号节点这一层idx 0执行ans[0] 3返回1回到2号节点这一层idx 1执行ans[1] 2返回2回到1号节点这一层idx 2执行ans[2] 1返回3。最终数组是[3, 2, 1]完美符合从尾到头的要求。递归方案里最容易被忽略的点是为什么“先递归、后赋值”就能反过来因为递归调用这里天然是一个栈内层的调用一定比外层先返回。后返回的外层函数反而先把值写进了数组的靠后位置。你要是把赋值放到递归调用之前那输出的就是正序了。这个“放前放后”的差别就是递归的精髓。但我要再次强调递归深度的隐患是真实存在的。题目限制链表长度0到1000010000层递归在所有常见操作系统上都很危险。某开发者朋友有一次在自己在VSCode里跑通了一万节点的测试但换到另一个默认栈更小的环境就崩了排查了半天才发现是递归爆栈。所以这个方案我更推荐用来理解原理不是推荐你作为第一解法。3.3 方案C实现反转链表后顺序遍历空间O(1)反转链表的迭代法也是一个经典模板这里直接给出实现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* reversePrint(struct ListNode* head, int* returnSize) { struct ListNode* newHead reverseList(head); // 先统计反转后的节点个数 int count 0; struct ListNode* p newHead; while (p ! NULL) { count; p p-next; } *returnSize count; if (count 0) { return NULL; } int* ans (int*)malloc(sizeof(int) * count); if (ans NULL) { return NULL; } // 反转后的链表顺序就是原来的从尾到头 p newHead; int index 0; while (p ! NULL) { ans[index] p-val; p p-next; } return ans; }反转的核心逻辑在reverseList函数里用prev保存前一个节点cur保存当前节点next保存下一个节点。每次把cur-next指向prev然后整体往后移动。这个“先备份下一个节点再改当前指针”的顺序是绝对不能乱的。你把next的备份放到修改cur-next之后那cur-next已经变了就找不到原来的下一个节点了。这段代码里第一个要注意的问题是head指针在反转后已经没有意义了因为原来的头节点变成了新链表的尾节点它的next指向NULL。所以后续遍历必须从newHead开始。第二个问题是反转操作改变了原链表结构。如果整个程序之后还要用原来的链表做别的操作那就有问题了。我在模拟面试时试过有位面试官明确说“不能修改链表结构”当时如果我选了方案C就得把整个思路推翻。所以用这个方案前一定要先确认题目要求和面试官的意图。4. 边界测试与C语言内存误区这些坑我全踩过写代码是一回事能扛住裁判系统的各种边界输入又是另一回事。下面我把这次折腾中遇到的所有边界和内存问题整理出来这几条是真正能帮你省时间的经验。4.1 边界用例清单不要只测长度为3的链表我刷题时习惯建一张自测表每道题至少跑通下面这些情况测试场景输入链表期望输出最容易出问题的地方空链表NULL空数组malloc(0)行为不确定要提前拦截单节点链表[5][5]数组下标是否越界递增序列[1,2,3,4,5][5,4,3,2,1]反转数组下标的计算重复值[7,7,7][7,7,7]无法通过值判断顺序对不对容易漏测长链表10000个节点逆序序列递归方案是否爆栈超大节点值[2147483647,-2147483648]逆序int类型是否能存下空链表和单节点是最容易翻车的。空链表时如果你没有在count 0时提前返回而是执行了malloc(0)再返回指针虽然一部分编译器允许但行为不可移植。我建议任何平台都统一写成return NULL。单节点链表则要验证index count - 1 0的逻辑也就是第一次填充就落在数组下标0上循环结束后index变成-1。这个看不出问题但如果你把while写成了do...while单节点时数组下标会先访问ans[-1]直接越界。很多编译器不会提醒你只有跑起来才知道错。重复值的测试很多人会跳过觉得“值一样测了也没意义”。其实恰恰相反正是因为值一样你才能通过打印每个位置的下标来验证顺序到底有没有写反。我踩过的一个真实教训是数组正序填好然后手动反转时多写了一次循环导致整个数组被翻了两遍输出和正序完全一样。如果测试用例里没有重复值这个错误很容易被误判成“正常”。4.2 C语言特有的内存误区returnSize、malloc失败、野指针returnSize忘记赋值是新手最高发的错误。判题系统拿到指针后会往这个地址读出数组长度。你不赋值它读到的可能是上一块内存残留的垃圾值结果就是数组越界访问。正确做法是在函数最开始就处理先统计完节点个数立刻把count写进*returnSize之后再开始申请内存。malloc返回值检查也不能省。很多人觉得刷题嘛malloc失败概率几乎是零所以随手就忽略。但C语言的面试题里评委经常故意追问“如果malloc返回NULL怎么办”。你代码里写了判空面试官会认可你的严谨没写他可能觉得你对C语言内存管理还没建立完整意识。所以两份代码里我都加了if (ans NULL)的分支这是给自己上的一层保险。还有一个细节在判题系统里你malloc出来的数组系统会自动帮你释放所以不需要free。但如果你在本地写测试程序那一定记得在打印完结果后free(ans)。我见过有人把判题系统里的代码原封不动搬到本地跑完又不释放内存一个测试函数循环100次内存涨了几十MB。这虽然不影响判题但作为C程序员随手释放自己申请的堆内存是基本素养。4.3 验证代码正确性的一个小技巧把链表画在三张纸上调试链表题时我个人的习惯是只在脑子里推演容易出错必须画图。具体做法是在纸上画出三个节点每个节点画两个格子一个放val一个放next指针。然后把代码里每一行操作对应的指针变化画出来。比如反转链表时prev、cur、next三个指针怎么移动画三遍基本全明白了。这个方法对检查递归也有效。递归难的不是逻辑而是你脑中要同时维护一条“递去”的线和一条“归来”的线。两件事混在一起就容易乱。画图时我把递去的路径用实线标归来的路径用虚线标赋值发生在虚线上就永远不会搞反。5. 面试追问题目一变你选哪种解法马上要换光会写原题还不够面试官几乎一定会换条件追问这才是真正拉开差距的地方。我总结过三种最常见的变体每种对应完全不同的解法取向。5.1 变体一接口加了const禁止修改链表如果函数的头指针参数变成const struct ListNode* head方案C就直接出局了。const语义上明确告诉你不能改动节点哪怕只是把next扭转一下也不行。这种场景下你只剩下两个选择辅助数组模拟栈或者递归。考虑到递归有栈溢出风险面试时我会先说“用辅助数组模拟栈”然后主动补一句“当然也可以用递归但链表长度10000时递归有爆栈风险所以这里我更倾向显式栈”。这一句话能同时展示你对const语义的理解和对空间复杂度的敏感度比闷头写代码要加分得多。5.2 变体二要求空间O(1)不能开额外数组这是另一个极端不让你用辅助数组还要逆序输出。如果仍然不允许修改链表那这道题在数学上就没有O(1)空间的解法。因为单链表本身只支持单向遍历逆序访问又没有任何“回头”信息你至少要保存一路往回走的路径信息。保存这个信息就需要O(n)空间无论用数组还是调用栈。所以面试官如果这么问你直接回答“不修改链表的前提下理论上不可能做到O(1)空间”是正确思路这不是你不会写而是确实存在下界。如果允许修改链表反转法就是唯一正解。这时候你不需要malloc任何数组遍历反转后的链表时边遍历边输出空间就是常数级别。三种方案里只有它能做到。5.3 变体三K个一组逆序打印链表比如链表是1-2-3-4-5-6-7-8要求每3个一组组内逆序打印输出就是3、2、1、6、5、4、8、7。这个问题本质上已经升级成“K个一组反转链表”的变种。你可以先实现一个局部反转函数处理从某节点开始的连续K个节点翻转后从新头开始遍历输出再跳到下一组的起始位置。这种变体考的是你能否把一道简单题的核心思想复用到复杂场景。如果原题你能清晰说出“栈/递归/反转”三者的关系那么变体题你大概率也能想到组内逆序输出 组内反转组间保持原顺序。它的实现细节比原题复杂很多但战略方向是一致的。还有一个容易被问到的变体打印到文件而不是返回数组。那就是把printf(%d , node-val)换成写文件操作其他逻辑一模一样这里就不再赘述了。6. 我的最终选择与一个画图小技巧综合下来我自己在判题系统里最终提交的是方案A也就是两次遍历加反向填充数组。原因很简单它不依赖递归栈不修改输入链表也不需要考虑malloc(0)等不确定行为内存可控逻辑清晰在所有边界情况下都能稳定运行。刷题不是为了炫技稳定通过才是第一目标。但如果你让我给初学者一个学习路径我会建议先手写方案A直到闭着眼都能写对然后把方案B的递归调用顺序彻底搞明白最后用方案C反向加深对链表指针操作的理解。三套方案全部吃透之后你再看其他链表题会有一种“来来回回就那么几种招式”的通透感。最后再分享一个我在面试中验证过的答题习惯拿到链表题先别急着写代码拿起笔在纸上画三个节点的链表标清楚每一步指针的指向。画完再动手写代码出错率至少降低一半。有的开发者觉得画图浪费时间实际上写出一个带野指针的版本再去调试浪费的时间比画图多得多。这个习惯我保持了很多年每次写链表的原地操作都靠它兜底。这道题的核心简单说就是“先进后出”四个字。想通了这一层代码只是把它翻译成C语言而已。