去年我把那套经典的数据结构MOOC又从头到尾刷了一遍编程练习题更是认认真真写完了。这套课配的在线评测平台题目质量很高尤其是第二讲“线性结构”部分的几道题看着不难真正上手写的时候才发现处处是坑。今天专门把第二讲的编程练习题拿出来聊聊讲讲每道题在考什么、怎么写才能不踩坑以及我调到吐血才总结出来的几个排查技巧。如果你正在刷这门课或者刚开始学链表、堆栈这一篇应该能帮你省下不少折腾时间。文章会按题目类型拆开讲先把关键思路吃透再上实操代码最后集中说常见问题。重点针对的是第二讲对应的几个核心练习题有序链表合并、一元多项式的乘法与加法运算、链表反转、弹出序列判断。1. 第二讲到底在考什么整体思路与题量地图1.1 为什么第二讲突然“上强度”第一讲介绍完抽象数据类型和算法复杂度更多是让你建立概念。到了第二讲知识点一下子落到线性表、堆栈、队列这些具体结构上配套编程题也从“读懂代码”变成了“手写结构”。很多人的第一感觉是链表不就几个指针指来指去吗结果一写就懵。原因在于第二讲的练习题没有一道是单纯背代码的它们共同指向同一个核心能力——用指针操作真实内存结构并保证极端情况不崩。这和平时刷的那些数组题完全是两种思维模式。MOOC里的视频讲的是原理和伪代码但评测平台考的是你能不能把这些伪代码变成可以运行的C语言程序。我见过很多同学视频看得明明白白一打开代码编辑器就不知道从哪下手。这个阶段正常的别慌把下面几道题逐个攻破线性结构就算真正入门了。1.2 四道经典题目各自在练什么第二讲配套的编程题通常包含四道核心题最大子列和那类题属于第一讲复杂度内容这里不展开我按个人认为的难度递增排序题号题目考察核心推荐用时线性结构1两个有序链表序列的合并带头结点链表的指针操作30分钟线性结构2一元多项式的乘法与加法运算链表构造、插入、同类项合并1小时线性结构3链表的反转分组逆转、边界处理1.5小时线性结构4出栈序列的合法性判断堆栈模拟40分钟这四道题是有递进关系的先学会最简单的链表合并再上手多项式的动态插入接着挑战反转这种需要精细控制指针的题最后用堆栈把思维从“结构”扩展到“状态”。把它们全写完你对“指针就是地址”“内存是手动管理的”这两件事会有全新的体感。2. 核心细节解析链表题目绕不开的三个套路2.1 带头结点链表几乎所有题的正确打开方式第二讲的大部分链表题输入都明确要求使用带头结点的链表。头结点不是第一个数据节点而是一个不存数据的哨兵节点它的作用是让链表在空和非空两种状态下保持操作逻辑一致。我见过太多同学在这个地方吃亏。比如合并两个有序链表如果不用头结点你需要单独判断“新链表是不是空”来决定第一个节点怎么挂代码里到处都是if (head NULL) else分支写得又长又容易漏。带头结点之后只需要维护一个tail指针tail-Next永远指向当前最后一个节点一切就都顺畅了。另一个容易被忽略的细节是新建链表节点时一定要先malloc再赋值。很多初学者直接声明一个结构体变量就往下走然后发现链表根本连不上。链表之所以叫链表就是因为每个节点都是动态申请的独立内存地址靠指针串起来。你要是只用一个栈上的局部变量每次循环结束变量就销毁了链表自然断掉。2.2 别用递归写链表反转这道题的两种常规解法链表反转这道题如果你习惯用递归思路会很顺先反转后续节点再把当前节点挂到后面。但对于第二讲这道题来说题目要求每K个节点反转一次最后不到K个的尾部节点保持原顺序用递归反而别扭因为你要处理“组”的概念递归天然不适合这种分段处理。所以这道题我强烈建议你用静态链表循环反转的思路而不是动态链表递归。静态链表的意思是用一个结构体数组存所有节点数组下标就是节点地址结构体里存数据Data和下一节点地址Next。这种做法的好处是你能像数组一样随机访问节点反转的时候不需要真的移动节点只需要改Next指针即可。核心方法分为三步先遍历一遍确认总节点数和有效节点数顺便丢弃不在链表上的多余节点然后从第一个有效节点开始每K个为一组做区间反转最后处理不足K个的尾段保持原顺序。反转一组节点时用一个pre指针指向本组第一个节点前面的那个节点再用cur和next两个指针做局部的三指针翻转。// 伪代码K个一组反转的核心翻转逻辑 // pre: 当前组第一个节点之前的节点地址 // cur: 当前正在处理的节点 // next: cur的下一个节点 while (当前组内已处理节点数 K) { next nodes[cur].Next; nodes[cur].Next pre; // 把当前节点指向前一个节点 pre cur; cur next; 当前组内已处理节点数; } // 循环结束后pre指向原来的第K个节点它就是新组的头 // 原组第一个节点的新Next应该指向下一组的第一个节点这里有个细节程序里节点地址要求按5位补零输出比如地址 00123 要输出“00123”。用printf(%05d, addr)就能实现别手写补零逻辑容易出bug。2.3 静态链表比动态链表在本题中优势明显第二讲的链表反转题目有一个很特殊的地方输入给出的节点地址并不连续有些节点甚至根本不在链表上浪费的节点。如果用动态链表你得先按地址把它们串起来然后还要处理哪些节点不在链上的逻辑非常痛苦。用静态链表则可以直接通过数组下标访问节点判断当前节点是否在链上的标准就是节点的Next是否被更新过。这道题我用静态链表一次就过了而第一次用动态链表写光是判断无效节点就让我调了很久。静态链表的代码模式也很简单定义一个大小为100005的node数组数组下标就是节点地址结构体里存data和next两个int值。读入时直接node[addr].data data; node[addr].next nextAddr;。遍历时用一个游标从给定的头地址开始不断取node[cur].next直到-1为止。这一套下来完全不需要malloc也不需要担心内存泄漏很适合竞赛和评测环境。3. 实操过程与核心环节实现四道题逐个击破3.1 有序链表合并20行代码解决的经典操作题目要求读入两个有序链表合并后输出一个新链表同时要求L1和L2在输出结束后指向空链表。最初我写这个题时总是想新建一堆节点后来发现完全没必要——合并的过程本质就是把两个链表的节点重新串联不需要申请任何新节点。List Merge(List L1, List L2) { List head (List)malloc(sizeof(struct Node)); // 头结点 List tail head; List p L1-Next; List q L2-Next; while (p q) { if (p-Data q-Data) { tail-Next p; p p-Next; } else { tail-Next q; q q-Next; } tail tail-Next; } tail-Next p ? p : q; L1-Next NULL; L2-Next NULL; return head; }这段代码的核心思路是谁小就把谁挂到新链表的尾部不管谁空了直接把剩余整条链接到尾部。注意输入输出函数要求用Print函数单独写别把所有输出都堆在main里。这里最容易被判错的点是最后两行L1和L2的Next必须置NULL。题目里明确要求输出后原链表为空很多同学漏了这一步导致Merge函数返回后原链表还残留着节点在线评测直接给你答案错误。3.2 一元多项式的乘法与加法一题练会动态插入和同类项合并这道题是第二讲里综合性最强的一道。它要求你用链表存多项式实现加法和乘法输出按指数降序排列的结果。加法部分的本质还是归并。两个多项式都按指数降序排列了那么用两个指针分别扫描比较当前节点的指数指数相等就系数相加指数不同就挂指数大的那个节点。这里要注意如果系数相加后变成0这个节点必须被丢弃不能留在结果链表里否则输出会多一项“0 x^n”。乘法部分更考验代码组织能力。最自然的做法是两层循环结果链表初始为空对于A多项式的每一项都与B多项式的每一项做乘法把得到的节点插入结果链表的正确位置。由于每个乘积项的指数可能相同所以插入时要先找位置同指数的合并系数不同指数的插在合适位置保持降序。// 乘法核心伪代码错误示范直接尾插会乱序 for (p A; p; p p-Next) { for (q B; q; q q-Next) { temp_coef p-Coef * q-Coef; temp_exp p-Expo q-Expo; // 绝不能直接 tail-Next temp; tail temp; // 必须调用 Insert(temp_coef, temp_exp, resultList); } }我最初图省事先把所有乘积项直接尾插进结果链表最后再排序合并结果代码又长又容易出bug。后来改成写一个Insert函数每次插入时遍历结果链表找到该指数对应的位置已经存在同指数节点就合并系数否则插在合适位置。这样写虽然每次插入都是O(n)但胜在逻辑清晰出错概率低。题目数据量不大完全够用。3.3 链表反转从思路到AC的完整拆解反转链表这题第一次做确实容易懵因为K个一组反转不是单纯整个链表反转。我记得我第一次写的时候反转函数写着写着就把自己绕进去了。推荐的做法是分两个函数一个计算有效节点总数一个做反转。计算有效节点时要注意输入可能有孤立节点这些节点不在链上反转时不能算进去。我只需要从头地址出发沿着Next指针走数到-1为止得到的就是有效节点数。反转的思路可以这样理解想象你有一串珠子节点每K个珠子为一组每组内部把项链线反向穿一遍组与组之间保持原有连接顺序。实现上最稳妥的方法是新链表逐个摘节点法从原链表的前端依次摘下节点头插到新链表头部这个过程天然实现了反转。但因为是K个一组所以每次只能连续摘K个摘完一组后新链表的尾部要和下一组连接。我用静态链表实现时核心是维护几个关键变量保存原来链表的头地址、保存当前组的第一个节点、保存上一组的最后一个节点。每组反转内部用循环修改Next循环结束后把本组最后一个节点的Next修改为下一组的头地址。// 每K个反转一次的示意代码静态链表版 int reverseList(int head) { // 把整个需要反转的链表分成若干组 // 每组内部反转后组首变组尾组尾变组首 // 用 lastGroupTail 记录上一组的结尾用它连到当前组的新开头 // 注意第一组反转后产生的头就是最终结果链表的头 for (int i 0; i groups; i) { 反转当前组内部的 Next 指向; 如果 i 0记录新头; 否则让上一组尾部的 Next 指向当前组的新头; 更新 lastGroupTail 为当前组的旧头新尾; } // 剩余不足K个的节点保持原样直接接到 lastGroupTail-Next return newHead; }这题的边界条件特别多K1、有效节点数正好是K的倍数、总数不足K、有孤立节点……每个都要单独想到。我当时就是用边界样例一个个试出来的。做题时强烈建议自己构造几个特殊输入验证一下光看数据是对的还不算完。3.4 出栈序列合法性判断用模拟法最省心这题给你一个容量为M的堆栈要求判断一个输出序列是否是1到N的合法出栈序列。你会得到一个序列你需要用程序判断它是否能用容量为M的栈产生。最直观的解法是模拟入栈过程用一个栈从1开始依次把元素压入栈中。每次压入一个元素后检查栈顶是否等于当前要输出的那个数如果相等就弹出然后继续检查下一个要输出的数。如果某次需要栈顶元素等于目标但栈已经满了或者已经把所有N个数都压进去了还是没找到说明这个序列不合法。我写这题时遇到一个典型教训不能只用一个while循环从头走到尾。比如当前要输出5你从1开始压栈压到5时栈顶是5弹出去后下一次要输出3但此时3已经被压在栈底出不来所以这个序列非法。这个判断要在每一步循环里反复进行而不是检查完第一个数就完事了。这道题用数组模拟栈写起来飞快而且不容易出错。千万注意M不等于N栈容量可能小于N所以判断栈满的条件和判断元素用完的条件要分清楚。4. 常见问题与排查技巧实录4.1 段错误十有八九出在scanf返回值上我之前写链表合并题时程序本地跑得好好的一提交就段错误。后来发现是读数据的问题。题目输入可能有多组数据用while (scanf(%d, n) ! EOF)这句话时必须小心一旦scanf返回值不是1说明没读到整数循环内如果继续用n去malloc或者操作数组直接越界。正确写法是在循环开头判断返回值再决定是否继续。另外一个和scanf有关的坑是指针变量取地址。比如你定义了intp用scanf(%d, p)是合法的但很多人会不小心写成scanf(%d, p)这种错误编译器不会报错因为p的类型是int*在部分编译环境下能通过警告继续运行但运行结果完全不对。我排查这种问题的方法是用文本编辑器全局搜索“p”这种写法一眼就能看出来。4.2 输出格式的坑补零、空格、换行一个都不能错在线评测对输出格式极其严格。链表反转题的节点地址要5位补零我第一次写成了printf(%d, addr)结果前导零全丢了输出对不上。这是最简单也最容易忽略的错误每道题的输出都要读三遍格式说明。多项式那道题要求每项之间有一个空格但不能有行末空格如果结果为零多项式要输出“0 0”。我建议单独写一个输出函数内部统一处理空格逻辑把第一项的标记位设为1之后每一项都在前面加一个空格。这样就不会出现行末多空格的问题。4.3 常见问题速查表现象可能原因解决方法合并链表后原链表还在没把L1和L2的Next置NULL函数返回前手动置空反转结果多出或丢失节点有效节点统计错误包含孤立节点从头地址起数到-1不要数所有输入节点多项式输出多出0项系数合并后为0未删除合并后判断是否为0为0则释放节点出栈序列判断错误栈满判断早于目标匹配先压栈压栈时判断满再弹栈匹配补零输出显示为数字没使用%05d格式化统一用printf(%05d, addr)4.4 调试链表相关题的三个独门技巧链表题调试起来比数组题难因为你不能直接在调试器里看到完整的链表结构。我的做法是写一个debugPrint函数专门用来输出链表的所有节点地址和数据在关键操作前后各调一次对比输出结果就能定位问题。第二个技巧是画图。不要嫌麻烦反转链表那道题我在草稿纸上画了三个组的状态图每一步的pre、cur、next分别指向哪里画完再写代码思路就清晰多了。第三个技巧是善用注释。做题时很多人随手写代码注释全部省略写错之后回头读代码要花大量时间。我后来养成的习惯是在处理指针改变指向的那几行代码上一定用注释标明“现在pre指向XXXcur指向XXX接下来要做什么”。这个习惯看着慢实际写题效率反而高。5. 一些实操心得四道题刷下来我最深的感触是数据结构这门课看视频只能给你40分的理解剩下的60分全靠写代码补。第二讲的线性结构看起来是最简单的部分但恰恰是链表和堆栈这两个基础结构把很多人的代码功底照出了原形。如果时间有限我建议优先把“有序链表合并”和“多项式乘法与加法”写透这两题涵盖了链表节点操作、插入删除、边界判断的绝大多数套路。反转链表和出栈序列判断属于进阶应用等基础牢了再挑战也不迟。最后分享一个小技巧写完一道题如果AC了别急着做下一题把代码里所有的if条件逐个翻出来想想如果删掉某个条件会不会出错。这个“反向验证”的过程能帮你真正理解每行代码存在的意义。我自己就是用这个方法把四道题从“碰巧过了”变成了“知道为什么这么写”之后再遇到链表相关的综合题写起来顺手很多。