去年我把那套经典的数据结构MOOC又从头到尾刷了一遍，编程练习题更是认认真真写完了。这套课配的在线评测平台题目质量很高，尤其是第二讲“线性结构”部分的几道题，看着不难，真正上手写的时候才发现处处是坑。今天专门把第二讲的编程练习题拿出来聊聊，讲讲每道题在考什么、怎么写才能不踩坑，以及我调到吐血才总结出来的几个排查技巧。

如果你正在刷这门课，或者刚开始学链表、堆栈，这一篇应该能帮你省下不少折腾时间。文章会按题目类型拆开讲，先把关键思路吃透，再上实操代码，最后集中说常见问题。重点针对的是第二讲对应的几个核心练习题：有序链表合并、一元多项式的乘法与加法运算、链表反转、弹出序列判断。

1. 第二讲到底在考什么：整体思路与题量地图

1.1 为什么第二讲突然“上强度”

第一讲介绍完抽象数据类型和算法复杂度，更多是让你建立概念。到了第二讲，知识点一下子落到线性表、堆栈、队列这些具体结构上，配套编程题也从“读懂代码”变成了“手写结构”。

很多人的第一感觉是：链表不就几个指针指来指去吗？结果一写就懵。原因在于，第二讲的练习题没有一道是单纯背代码的，它们共同指向同一个核心能力——用指针操作真实内存结构，并保证极端情况不崩。这和平时刷的那些数组题完全是两种思维模式。

MOOC里的视频讲的是原理和伪代码，但评测平台考的是你能不能把这些伪代码变成可以运行的C语言程序。我见过很多同学视频看得明明白白，一打开代码编辑器就不知道从哪下手。这个阶段正常的，别慌，把下面几道题逐个攻破，线性结构就算真正入门了。

1.2 四道经典题目各自在练什么

第二讲配套的编程题通常包含四道核心题（最大子列和那类题属于第一讲复杂度内容，这里不展开），我按个人认为的难度递增排序：

这四道题是有递进关系的：先学会最简单的链表合并，再上手多项式的动态插入，接着挑战反转这种需要精细控制指针的题，最后用堆栈把思维从“结构”扩展到“状态”。把它们全写完，你对“指针就是地址”“内存是手动管理的”这两件事会有全新的体感。

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; }

这题的边界条件特别多：K=1、有效节点数正好是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 常见问题速查表

4.4 调试链表相关题的三个独门技巧

链表题调试起来比数组题难，因为你不能直接在调试器里看到完整的链表结构。我的做法是写一个debugPrint函数，专门用来输出链表的所有节点地址和数据，在关键操作前后各调一次，对比输出结果就能定位问题。

第二个技巧是画图。不要嫌麻烦，反转链表那道题，我在草稿纸上画了三个组的状态图，每一步的pre、cur、next分别指向哪里，画完再写代码思路就清晰多了。

第三个技巧是善用注释。做题时很多人随手写代码，注释全部省略，写错之后回头读代码要花大量时间。我后来养成的习惯是：在处理指针改变指向的那几行代码上，一定用注释标明“现在pre指向XXX，cur指向XXX，接下来要做什么”。这个习惯看着慢，实际写题效率反而高。

5. 一些实操心得

四道题刷下来，我最深的感触是：数据结构这门课，看视频只能给你40分的理解，剩下的60分全靠写代码补。第二讲的线性结构看起来是最简单的部分，但恰恰是链表和堆栈这两个基础结构，把很多人的代码功底照出了原形。

如果时间有限，我建议优先把“有序链表合并”和“多项式乘法与加法”写透，这两题涵盖了链表节点操作、插入删除、边界判断的绝大多数套路。反转链表和出栈序列判断属于进阶应用，等基础牢了再挑战也不迟。

最后分享一个小技巧：写完一道题如果AC了，别急着做下一题，把代码里所有的if条件逐个翻出来，想想如果删掉某个条件会不会出错。这个“反向验证”的过程能帮你真正理解每行代码存在的意义。我自己就是用这个方法，把四道题从“碰巧过了”变成了“知道为什么这么写”，之后再遇到链表相关的综合题，写起来顺手很多。