数据结构这门MOOC，第二讲的编程练习题几乎算得上是一道实打实的“劝退门槛”。很多同学学完了线性表的理论知识，觉得自己数组、结构体、指针都懂，结果一打开练习题，面对链表操作直接卡住，实验课从下午三点坐到晚上八点，就为了一个“PNODE”到底要不要二级指针的问题。这讲内容远不只是让用户完成几道题，而是逼着每个人把“书上读得懂的语言”变成“机器认得出的代码”。这篇博文就来拆解第二讲那些入门必刷题背后真正想要考的点，以及我反复重写后最值得注意的操作细节。
1. 第二讲整体设计的思路拆解
1.1 为什么一进入第二讲，编程题的难度突然跃升
第一讲通常是简单的输入输出、基本循环、函数封装，练的是“把思路用代码写出来”的底子。但是第二讲标题里基本都会挂上“线性表”，这就不是简单的逻辑训练了。线性表是数据结构的第一个真正的抽象模型，配套的存储实现又分为顺序表和链表。顺序表说白了是连续数组的操作，辛苦但直观；链表则引入了指针、动态申请内存、节点之间的“链式”关系，难度提升的不是一点点。
MOOC第二讲编程练习题的设计者喜欢在这里安排两类题：第一类是“实现某种结构上的操作”，比如创建链表、插入节点、删除指定位置的元素；第二类是“基于线性表完成一个特定任务”，比如合并有序序列、求多项式的和。前者考结构理解，后者考算法思维和编码结合。这两类题同时出现，目的是让学习者不再只是背接口，而是自己把“存储结构 + 逻辑操作”捏成一个完整解决方案。某个高校的教学团队在做这套题的时候，往往还会把输出格式卡得很死，就是为了让学生体会到，数据结构题不只是“做对”，还要做到和描述严格一致。
1.2 编程练习题与理论课的配合逻辑
很多人以为刷题只是验证自己会写了，其实第二讲的编程题还扮演一个角色：来替代传统课堂里的“思考题”。理论课讲单链表的插入和删除时，课件上会有很漂亮的示意图，箭头指来指去，看的时候觉得很有道理。但一到自己写代码，会突然发现不知道应该先处理哪个指针，不知道要不要保留某个临时变量。编程题就是专门把这种“看得懂”变成“写得对”。
具体来说，第二讲的题在刻意训练三个能力：
- 第一种能力是“从接口到实现的推演”。题目会给定函数签名，比如要求写一个插入函数，传入链表头节点指针和插入位置，你需要自己决定内部怎么写。这跟后续工程实践里的接口设计很像，提前感受一下不是坏事。
- 第二种能力是“边界条件的审视”。链表题里到处都是边界：空链表怎么办？只有一个节点怎么办？插入到第0个位置怎么办？删除最后一个节点怎么办？教科书上简洁的伪代码根本不会告诉你这些，只有自己提交、报错、再试，才能记住。
- 第三种能力是“内存和指针的可视化”。指针变量本身存的是一个地址，赋值操作改变的是指针的指向，不是拷贝一份数据。这个概念不亲自写链表题，真的很难体会。
所以，与其说第二讲编程题是课后作业，不如说是一场面向结构思维的专项训练。它想要的结果不是“做出来”，而是让每个提交通过的人，对内存里的数据排布有了具体的画面感。
2. 核心题型解析与应掌握的解题思路
2.1 顺序表类题目：数组操作中的“细节魔鬼”
第二讲里顺序表类的典型题目有：顺序表插入删除、二分查找变体、有序表去重等。接口往往要求返回新的长度或者移动后的状态。这类题看起来比链表简单，毕竟就是数组下标换来换去，但真正容易丢分的在两个地方。
第一是插入位置合法性的判断。比如长度为n的顺序表，可插入位置是0到n之间，写循环做移位的时候，如果从前往后移，会把后面没处理的元素覆盖掉。正确的姿势是从后往前移动元素。第0个位置插入，要先把第n-1个元素移动到第n个位置，再把第n-2个移动到第n-1个，一直到把原来的第0个移到第1个，最终才能给新元素腾出第0位。做题时不画一个五元素的数组，很容易写错方向。
第二是删除元素后的长度更新。很多同学删除完元素，只把后面的元素往前挪，忘了把最后的旧值处理掉，或者忘了更新长度变量。顺序表结构体里一般有两个成员：数组指针和当前长度。删除时应该是从删除位置向前覆盖，最后让长度减1。但要注意，如果后续还需要遍历这个顺序表，最好把最后那个“逻辑上已经不存在”的元素至少置个默认值，不然调试时数据干扰视线。
顺序表的另一类经典题是“原地删除重复元素”，要求空间复杂度O(1)。思路是用双下标，一个遍历，一个记录新表长度，遇到不重复的元素就往前面写。这个思路其实跟链表去重也相通，值得好好练一下。我见过有同学在这道题上用每次删除都移位的方法，复杂度直接飙到O(n^2)，在数据规模一大就超时。双下标一旦想通，这类题基本就是模板。
2.2 带头结点链表的操作：头结点的价值在哪里
PTA风格的上机题里，链表题几乎清一色强调“带头结点”。头结点不是存储数据的第一个节点，而是一个方便统一操作位置逻辑的哑节点。它的最大价值在于：当链表为空时，你依然持有一个非空的头指针，插入和删除第一个元素时不需要特判“这是不是第一个”。第二讲大量题目的前置条件就是带头结点，这是教学设计里的一个重要伏笔。
我见过不少人做题时把头结点和首元结点混为一谈。带头结点的链表里，头结点的next指向首元结点，头结点本身的data通常不使用。当遍历一个带头结点的链表时，应该从 head->next 开始，而不是从 head 开始。这个错误非常经典：看起来输出多了一个头结点值，或者某种情况下访问了无意义的内存。建议一上来就自己写一个带头结点的链表初始化函数，把head->next = NULL，然后逐步练习各种插入，把“头结点存在只是为了操作方便”这层意思吃透。
在做“按序号查找”、“按值查找”这类题目时，头结点还会影响计数的起点。有序号从0开始和从1开始两种，题目描述里都会写清楚，但很多人不看细节，想当然用for循环从1开始计数，一提交就错。建议每次都先写一个空链表和长度为一的链表做样例，用纸笔比划一下第0个和第1个的区别。
2.3 链表反转与合并：第二讲里真正拉开差距的两座山
链表反转是所有后续算法题的基础。实现方式有三种最常用：迭代反转、递归反转、以及借助数组反向重建。第二讲的题目通常默认要求迭代反转，核心操作是三个指针：当前节点、前一个节点、后一个节点。每步循环里，先把当前节点的next保存下来，再让当前节点的next指向前一个节点，然后把prev和curr同时向后移动。如果不先保存next，指针一旦改了指向，后面的节点就找不到了。这句话我每届都要重复无数遍：链表反转的本质不是交换，而是逐个修改指针方向。
另一个高频压轴题是两个有序链表的合并。常见的实现有两种：不申请新节点，单纯把两个链表的next指针“拉链式”地织到一起；或者每取一个节点就malloc出一个新节点接到结果链表上。OJ判题通常两种都接受，但前者更贴近“操作结构“的本意，后者反而在你的内存管理不熟时制造更多麻烦。合并的核心是三个工作指针：p指向链表1当前节点，q指向链表2当前节点，r指向结果链表的尾节点。每次比较p和q的data，把值较小的节点接在r后面并移动对应指针，直到某个链表走完，再把剩下那串直接接到末尾。关键点是最后一截的“接尾巴”不要再去遍历，直接让r->next等于剩余链表的头即可。
这两道题做熟以后，二叉树遍历、图的最小生成树算法里的“节点连接”思路都会顺很多。因为它们锻炼的都是同一件事：在一个链式结构上，不靠数组下标，只靠“保存、修改、移动”三个动作来维护正确的前后关系。
3. 实操：从读题到提交的完整闭环
3.1 先写样例再动手写代码，比什么都重要
第二讲最忌讳的就是打开题目，看几眼，直接开写。这套MOOC的题目描述往往很长，尤其喜欢用“给定某结构定义，实现某函数”的格式。我最推荐的做法是：先把输入样例和输出样例抄到本地，跑一遍脑子里的流程图，确信自己知道输入如何一步步变成输出，再开始写代码。特别是链表类题目，一定要在纸上画出一串节点，标注每个指针的变化过程。不要嫌麻烦，你写代码的时间大概率比画图的时间长得多。
比如一道典型的“有序链表插入”题目，输入可能分别给出一个已排序链表和一个新节点值，要求插完之后依然有序。先手动模拟一下：空链表插这个值、插在头部、插在中间、插在尾部，这四种情况都覆盖到，心里就有底了。起草时甚至可以先用注释把四个分支写出来，再逐行填充。这个习惯从这种基础题养起，后面做复杂题时会非常受用。
3.2 函数接口题怎么拿到要求的输入
MOOC编程题库喜欢考“实现一个函数”而不是“写完整程序”。这就意味着读输入和主流程框架已经由系统给定，你只需要在指定的函数体内补齐逻辑。很多人一上来不知道从哪里读数据，如果本地没有官方给的测试程序，可以自己补一个。在函数接口题里，你挑战的重点是算法的正确性，不需要自己去处理scanf的返回值、字符串末尾换行这些细节。
实际操作时的难点常在于参数形态。比如函数参数是“List L”，这个List很可能是没有定义的结构体指针，你需要从系统提供的头文件或者题目描述里找到结构的定义。我习惯的做法是：不管题目怎么说，先用一段本地测试代码实例化几个节点，手动建立一条链表，调用自己要实现的函数，看看返回值和预期是否一致。这样可以避免“代码结构对但根本没能在真实环境下运行”的尴尬。
函数题还有一种坑是函数名大小写或参数顺序与声明不一致。编译器找不到符号或者类型不匹配时会报错，这类错误有时并不好懂。建议提交前认真对照题目里的函数原型，不要凭记忆写。尤其当题目给出的形参名是英文但你已经习惯了另一套命名的时候，很容易出现“看起来差不多”的偏差。
3.3 内存申请与释放：每一步malloc都要能追问“谁负责free”
链表题的每个节点大概率都需要动态申请内存。很多只做Java或Python题目的同学第一次接触C的链表题会非常不适应，因为这里没有垃圾回收，malloc出来的内存必须对应一次free，否则就有内存泄漏。MOOC的OJ通常不会对内存泄漏做严格检测，但后续课程比如操作系统实验，就会因为这种坏习惯吃大亏。
第二讲里常见的动态内存错误有两类。
- 一类是忘记malloc直接使用未初始化的指针。定义了一个 List node; 就以为有了节点，实际node只是指向某个内存地址的变量，里面可能是任意垃圾值。正确做法是 List node = (List)malloc(sizeof(struct LNode));，之后再给node->data和node->next赋值。
- 另一类是delete或free后用错了指针。free(p)之后，p指向的内存已经被释放，再去读p->data会触发未定义行为，常见表现是随机崩溃或者输出莫名其妙的值。修正办法是free之后把p置为NULL，养成良好的习惯。
还有一个很多人忽视的细节：如果题目要求你“删除节点并释放内存”，但在OJ环境里，测试程序可能依然持有这个节点地址用于检查。某些题目允许你不free，直接绕过逻辑删除也行，但那样一旦数据量大了，内存会涨得很快。稳妥做法是：明确每个节点的主人是谁，谁调用删除函数，谁负责释放。个人经验是写链表操作时把“delete与free”合进一个函数，不要在外部自己malloc一块内存又期望别人释放。
3.4 核心代码示例：带头结点的单链表反转
这里给一段适合第二讲练习的带头结点单链表反转代码，假定结构定义是：
#include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; struct LNode *next; } LNode, *List; void ReverseList(List L) { if (L == NULL || L->next == NULL) { return; } LNode *pre = NULL; LNode *cur = L->next; while (cur != NULL) { LNode *nxt = cur->next; cur->next = pre; pre = cur; cur = nxt; } L->next = pre; }代码核心是这三行：
LNode *nxt = cur->next; cur->next = pre; pre = cur; cur = nxt;第一行保存当前节点的原本后继，第二行把当前节点的next改为指向前面节点，第三行和第四行整体后移两个指针。很多新手在第二步修改完cur->next之后，直接用了cur->next取后继，结果当然是空指针，因为next已经被改了。先保存nxt，就是解决这种自毁路径问题的标准手段。
反转结束之后，不能忘记更新头结点的next。因为原首元节点成了尾节点，新首元节点是原来的尾节点，如果不更新L->next，整个链表逻辑上还是老顺序，头结点会悬空指向一个已经“反了”的节点。我见过很多次反转函数写得对，但就是因为头结点没接回去，测试结果仍然是原序或随机乱序。
3.5 调试链表题最快的方式：加打印而不是单步跟
很多初学者习惯用IDE的断点单步去跟链表程序，链表结构一长，变量窗口里指针关系根本看不清楚。我个人更推荐“打点法”：在每个关键循环或递归出口加一个printf，打印当前节点的数据和指针，然后用小数据跑一下。比如反转链表可以用一个长度4的链表，打印每一步后的pre、cur、nxt地址，一眼就能看出指针方向对不对。
还有一个小技巧：很多OJ题目有输出函数，比如PrintList(List L)，你可以在自己代码里调用它看看当前链表状态。不过要小心不要把这个额外输出留在提交版本里，否则OJ会因为输出格式不符而判错。我一般用一个条件编译或者临时注释，本地调试的时候打开，提交前关掉。
4. 常见错误与排查方案
4.1 段错误(Segmentation Fault)的第一现场：到底是谁的空指针
第二讲练题阶段，段错误几乎是最常见的提交结果。它通常出现在访问了非法内存地址时，也就是指针指向了NULL或者已经被释放的内存。链表题段错误的典型排查顺序：
- 先检查是不是在解引用NULL指针。比如遍历链表的while循环写成 while (p->next != NULL) 时，如果p本身是NULL，访问p->next就已经崩了。应该写成 while (p != NULL && p->next != NULL) 或者先判断p。
- 再检查头结点是否为空。有些初始化流程里，如果L没有malloc就传入函数，任何L->next都是未定义行为。
- 最后检查有无访问已经free的节点。前面说过，free之后最好置NULL，就是防止这类错误。
一个比较隐蔽的段错误是链表出现“环”。比如反转链表时，如果某步没有先保存nxt，修改next之后，后面的节点可能再也无法顺序访问，遍历会一直循环，直到越界崩溃。这种问题用断点很难发现，但通过打印节点数量就能快速看出“节点数比预期多”或者“程序卡住”。
4.2 输出格式错误：空格和换行也是判题点
OJ题目对输出格式的严格程度常常让新手崩溃。链表题输出时，通常每两个元素之间有一个空格，行末不能有多余空格。很多同学函数逻辑正确，就因为多打了一个空格被判格式错误。解决办法是在本地写一个“按照题目要求格式输出”的小工具函数，专门处理末尾空格。
我的习惯是：
void PrintList(List L) { if (L == NULL || L->next == NULL) { printf("\n"); return; } LNode *p = L->next; while (p != NULL) { if (p != L->next) { printf(" "); } printf("%d", p->data); p = p->next; } printf("\n"); }用“第一个元素前不加空格，后面每个元素前加空格”的方式来避免尾部多余空格，这比“每输出一个元素后加空格，最后再退格”靠谱得多。
4.3 常见问题速查表
| 症状 | 可能原因 | 排查方向 |
|---|---|---|
| 提交即段错误 | 空指针解引用；链表未初始化 | 检查所有解引用前是否判空 |
| 输出多出节点或死循环 | 头结点也被当作数据节点遍历了 | 确认从head->next开始遍历 |
| 反转后顺序没变 | 忘记把头结点next接到新首元节点 | 反转循环后更新L->next |
| 插入后链表断裂 | 未保存后继节点就修改next | 先用临时变量存原next |
| 部分用例超时 | 链表本身太长；循环条件写错形成死循环 | 打印节点数观察是否正常终止 |
| 内存申请失败或泄漏 | 没有free；free后又使用 | 保持配对malloc/free习惯 |
这张表是我实际刷题整理出来的，几乎覆盖了第二讲80%以上的报错场景。每次卡住先对照这张表，比自己瞎改快得多。
5. 做题之外，更想分享的几点体会
5.1 先动手画链表图，再动手写代码
我的导师当年跟我说过一句很管用的话：链表题永远不要在脑子里空想，哪怕再简单的题也要画图。画图不需要精致，只要用方框代表节点，用箭头代表next指针，标上变量名。每改一次指针，用橡皮擦掉重画。这个过程多花五分钟，能省掉后面一小时的单步调试。尤其是后面学到树和图，这个习惯会一路受益。
实操中我发现一个特别好用的“画图指标”：当你画的图中，节点和边的数量跟代码里malloc的次数对得上，说明内存结构没乱；当你觉得某个节点“找不到了”，大概率就是代码里某个next被覆盖掉了。链表题的绝大多数错误，本质上都是“指针指向了你没预期的地方”，画图能让这种偏差无处遁形。
5.2 第二讲的题别只做一遍，定期重写很有用
这套题的魅力在于，它不会因为你做过一遍就变得索然无味。我建议隔两三周，再拿出一道当时觉得难的链表题，不看原来代码，重新写一遍。第二次写往往能明显感觉到自己比之前更熟悉指针操作步骤，甚至能写出更简洁的版本。这个“重新实现”的过程比看十遍答案都有用。
重写时也可以换一个实现角度。比如之前用迭代写的反转，这次试着用递归写；之前用“额外申请节点”做的合并，这次改成“原地拉链”。这种多视角练习，可以把一道题的思维迁移到不同场景。等你做到能反过来给别人讲清楚“这里为什么要先保存nxt”，这道题才真正算吃透了。
5.3 后续课程的衔接：第二讲是后面所有章节的底座
在MOOC课程体系里，第二讲结束之后马上就是栈和队列。栈和队列如果用链表实现，你会发现那不过是链表操作的特例：栈只允许在表头插入和删除，队列在一端插入另一端删除。如果第二讲的链表基本功不扎实，到栈和队列的实现中，很容易卡在“为什么这个函数要返回新的头结点指针”这种问题上。
再往后走，树的二叉链表存储、图的邻接表表示，本质上都是链式结构的延展。到那个时候你不会再害怕指针，因为你已经知道“每一个节点都持有指向若干个其他节点的指针”意味着什么。所以第二讲编程练习题，值得投入比理论课多两倍的时间去细磨。现在花时间把链表彻底搞懂，后面的学习会顺畅得多。
