数据结构第二章线性表课后习题全解：顺序表与链表算法精讲

1. 章节定位：为什么第二章是整本书的分水岭

先聊点题外话。严蔚敏老师的《数据结构（C语言版 第2版）》是国内计算机专业覆盖面最广的教材之一，也是很多学校考研指定的参考书。我当年备考的时候，身边至少有三种不同版本的答案资料在流传，有的复印模糊，有的题号对不上，有的代码风格跟教材差异太大。第二章线性表更是重灾区，因为这一章的课后题数量和类型都比较杂，从基础的概念题到需要手写完整算法的设计题都有，很多同学刷到一半就卡住了。

第二章之所以关键，是因为它承担了两个任务：一是帮你建立“逻辑结构”和“存储结构”的区分意识——同样是线性表，顺序存储和链式存储的增删查改效率完全不同；二是引入了大量后面章节会反复使用的编程范式，比如指针操作、动态内存分配、边界条件判断。换句话说，这一章如果代码功底不扎实，后面学栈、队列、串、树、图都会很吃力。我见过不少同学学到二叉树时回头补线性表代码的，效率反而更低。

这篇博文我按章节顺序，把第二章的课后习题分成“概念辨析题”“算法设计题”“上机实践题”三类来逐个拆解。重点放在需要写代码的题目上，每一题都会给出我的完整实现思路、C语言代码、以及我在实际运行中遇到过的问题。比较基础的判断题和填空题，我给出关键结论和理由。

2. 先吃透这两个底层概念再做题

2.1 顺序表和链表到底该怎么选

课后题里反复出现的一个问题就是“什么时候用顺序表，什么时候用链表”。很多同学只是机械地背结论，但做题时换个问法就不会了。我建议你从三个角度去理解这件事。

第一个角度是存储方式。顺序表在内存里是一块连续的区域，像电影院的连排座位；链表则是分散的节点，像停车场里随机停的车，通过指针把前后车位串起来。这个差异决定了顺序表支持随机访问，下标定位的时间复杂度是O(1)，而链表想找第i个节点必须从头开始数，最坏是O(n)。

第二个角度是插入删除操作。顺序表的插入和删除平均要移动一半的元素，链表只需要修改指针指向，从算法复杂度上看链表更优。但实际工程里不能只看复杂度，因为顺序表的内存连续特性对CPU缓存更友好，数据量不大时顺序表往往更快。我在处理一些学生项目时发现，数据量在一万以内，顺序表的实测性能经常反超链表。

第三个角度是存储密度。顺序表除了数据本身几乎没有额外开销，链表每个节点都要多存一个指针，存储密度低于顺序表。如果节点数据本身很小，比如只存一个int，那链表的指针开销甚至会超过数据本身。理解这三点之后，再回头看“设计一个算法判断一个线性表更适合用顺序表还是链表”这类题，你就知道该怎么答了。

2.2 C语言指针操作的三个易错点

第二章的算法设计题几乎离不开指针，尤其是链表部分。我批改学生代码时发现，最容易翻车的不是算法思想，而是指针操作的基础功底。这里列三个高频易错点。

第一个是“指针悬挂”。写过free(p)之后没有把p置为NULL，后面继续用p访问内存。这种错误在链表删除节点的题目里特别常见，你删掉了节点，但原指针还指向那块已经释放的内存，再次访问就是未定义行为。正确做法是先用一个临时变量保存下一个节点的地址，再释放当前节点。

第二个是“头节点”的处理。严蔚敏教材里的单链表默认带头节点，头节点不存储数据，只是方便统一插入删除的逻辑。很多同学做题时忽略了头节点的存在，导致边界判断出错。比如在一个带头节点的链表里，删除第一个数据节点和删除中间节点的代码可以完全一样，这是头节点最大的好处。

第三个是“引用与二重指针”的混淆。C语言里没有C++的引用，想在函数内修改主函数里的指针变量本身，必须传指针的地址，也就是二重指针。教材中的一部分算法实现用了C++的引用语法，但如果你用纯C环境，需要改成LinkList *L这种形式。这个问题在考研复试上机环节尤其容易踩坑。

3. 顺序表部分：课后习题算法逐题精解

3.1 逆置顺序表：一个原地算法，两种边界条件

逆置顺序表是第二章非常经典的一道题。题目要求不开辟新数组，把顺序表中的元素原地逆置。核心思路是双指针，一个指向表头，一个指向表尾，交换它们的值，然后头指针后移、尾指针前移，直到两个指针相遇。

#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SqList; void ReverseList(SqList *L) { if (L->length <= 1) { return; } int low = 0; int high = L->length - 1; while (low < high) { int temp = L->data[low]; L->data[low] = L->data[high]; L->data[high] = temp; low++; high--; } }

注意边界条件。长度是0或1时，直接返回，不需要任何操作。循环条件是low < high，如果写成low <= high，在偶数长度时中间两个元素会交换两次，等于白做。当然不影响最终结果，但属于多余操作，我在代码审查时一般会指出来。

这道题的时间复杂度是O(n)，空间复杂度是O(1)，是典型的“原地”算法。它还有一个变体，就是“前m个元素和后n个元素互换位置”，本质上是三次逆置：先把前m个逆置，再把后n个逆置，最后整体逆置。这个思路在很多公司笔试里会出现，建议顺手练一下。

3.2 删除所有值为x的元素：两种实现思路对比

这道题要求删除顺序表中所有值等于x的元素，并且尽量高效。最容易想到的做法是每找到一个x就把它后面的元素全部前移，但这样最坏情况时间复杂度是O(n²)，不够优雅。

更好的思路是“收集非x元素”。用一个变量count记录当前已经收集了多少个非x元素，遍历原表，遇到非x元素就把它放到位置count上，然后count加一。遍历结束后，把表长更新为count。这样一趟循环就能完成，时间复杂度O(n)，且不需要额外空间。

void DeleteAllX(SqList *L, int x) { int count = 0; for (int i = 0; i < L->length; i++) { if (L->data[i] != x) { L->data[count] = L->data[i]; count++; } } L->length = count; }

有个细节需要注意：如果顺序表中元素本身就是x，那我们就把“无用的元素”覆盖掉，不用管原来的值。但如果x出现得很频繁，count的增长速度会明显慢于i，后边的非x元素会往前覆盖，此时原来位置上的x已经被覆盖了，不会产生残留。这个算法是稳定的吗？严格说，它保持了非x元素的相对顺序，所以是稳定的。

3.3 删除有序顺序表中重复元素：快慢指针的典型应用

题目给的是一个非递减有序的顺序表，要求删除重复元素，使表中每个元素只保留一个。比如[1, 2, 2, 3, 3, 3, 4]变成[1, 2, 3, 4]。

思路是用两个下标i和j。i指向“结果表”的最后一个位置，j是遍历指针。初始时i=0，j从1开始。每次发现data[j]不等于data[i]，就把i加一，然后把data[j]复制到data[i]的位置上。

void DeduplicateSorted(SqList *L) { if (L->length <= 1) { return; } int i = 0; for (int j = 1; j < L->length; j++) { if (L->data[j] != L->data[i]) { i++; L->data[i] = L->data[j]; } } L->length = i + 1; }

这里比较的是data[j]和data[i]，不是data[j]和data[j-1]。因为data[i]始终指向当前结果表的最后一个元素，一旦遇到不同的值，说明新元素出现了，直接放到下一个位置就行。两者效果一样，但和data[i]比较的思路更容易推广到“去重后保留前k个”这类变体题。一个值得思考的问题是，如果把条件改成“删除所有重复出现的元素，即重复元素一个都不留”，算法该怎么改？比如[1, 2, 2, 3, 3, 4]变成[1, 4]。这就是LeetCode 82题，感兴趣可以挑战一下。

3.4 两个有序顺序表合并：谁的小，先放谁

合并两个非递减有序的顺序表，要求结果仍然有序。核心思路是双指针，从头开始同时遍历两个表，谁的元素小就先放进结果表里，然后对应指针后移。其中一个表遍历完后，把另一个表的剩余元素全部拷贝过来。

void MergeSqList(SqList A, SqList B, SqList *C) { int i = 0, j = 0, k = 0; while (i < A.length && j < B.length) { if (A.data[i] <= B.data[j]) { C->data[k++] = A.data[i++]; } else { C->data[k++] = B.data[j++]; } } while (i < A.length) { C->data[k++] = A.data[i++]; } while (j < B.length) { C->data[k++] = B.data[j++]; } C->length = k; }

注意这个实现里，如果A和B中有相等的元素，会优先取A的。这样结果表是稳定的，也就是相等元素的相对顺序和原始两个表里的顺序一致。合并操作的时间复杂度是O(m+n)，是归并排序的核心子过程，这个思路后面还会用到。我在做这道题时会额外检查一下C表是否足够大，也就是C的容量必须大于等于A.length + B.length，否则数组越界，但这种错误在上机时经常被忽略。

4. 链表部分：指针操作与算法设计全覆盖

4.1 头插法建立单链表：代码三行，坑有四个

用头插法建立单链表的过程很简洁，但初次接触的同学很容易犯几个低级错误。标准代码是这样的：

typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; LinkList CreateListHeadInsert(int arr[], int n) { LinkList L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; for (int i = 0; i < n; i++) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = arr[i]; s->next = L->next; L->next = s; } return L; }

第一个坑是忘记让s->next = L->next，这样新节点直接指向NULL，链表会断。第二个坑是忘记把L->next更新为新节点，这样新节点虽然创建了，但没有串进链表里，等于白做。第三个坑是头插法会导致数据顺序和输入顺序相反，比如输入[1, 2, 3]，链表里的顺序是3->2->1。有些题目要求头插法建立后按输入顺序访问，这就需要最后再逆置一次。第四个坑是申请节点后没有判断malloc是否返回NULL，在内存紧张时可能导致程序直接崩溃。

头插法的一个重要应用是“逆序输出链表”。如果题目要求从尾到头打印链表，可以通过头插法重新建立一个新链表，然后顺序打印即可。

4.2 两个有序单链表合并：一个指针让你少写一半代码

有些同学合并两个有序链表时会引入三个新指针，代码写得又长又容易出bug。其实可以复用两个链表原有的头节点，这样只需要一个新头指针和一条游走指针。

LinkList MergeLinkList(LinkList A, LinkList B) { LinkList C = A; // 复用A的头节点作为结果表的头节点 LNode *p = A->next; LNode *q = B->next; LNode *r = C; // r始终指向结果表的尾节点 C->next = NULL; free(B); // B的头节点不再使用，释放 while (p != NULL && q != NULL) { if (p->data <= q->data) { r->next = p; p = p->next; } else { r->next = q; q = q->next; } r = r->next; } if (p != NULL) { r->next = p; } if (q != NULL) { r->next = q; } return C; }

这里的r是整个算法的关键，它始终指向结果表的最后一个节点，每次把较小节点挂上去之后都要立即更新r。很多同学在循环里忘记更新r，导致后面的节点全部丢掉了。还有一点，循环结束后两个链表可能都还有剩余节点，要分别处理，不能漏掉。

这道题和顺序表合并思路完全一致，但链表只需要修改指针，不需要移动数据，时间复杂度同样是O(m+n)。我通常会让同学把顺序表和链表的合并放在一起对比学习，这样能明显感受到存储结构对操作方式的影响。

4.3 反转单链表：三指针法为什么比头插法更适合考试

单链表反转是第二章最不能绕过的题。两种常见方案：辅助空间法容易想到但空间复杂度不是最优；三指针法和头插法可以通过调整指针本身完成原地反转。

三指针法标准代码：

void ReverseLinkList(LinkList L) { LNode *prev = NULL; LNode *curr = L->next; LNode *next = NULL; while (curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } L->next = prev; }

注意三指针法的核心逻辑：先保存curr->next到next，再把curr->next指向prev，之后三个指针整体后移。如果不变量的顺序错了，链表就会断。我建议你在草稿纸上把每一步的指针变化画出来，画一遍基本就记住了。

另一种方案是头插法，思路是把头节点摘下来，然后遍历原链表，每遇到一个节点就把它插入到头节点之后。头插法的优点是符合直觉，缺点是改变了原来的节点连接关系，如果想保持原链表不变，就没那么方便。三指针法不改变原链表结构，只是改变了next方向，这也是为什么面试和考试中更推荐三指针法。

4.4 删除链表中最小值节点：双指针记录前驱

这道题的要求是删除单链表中数据域值最小的那个节点。思路是遍历一遍链表，记录当前最小值节点和它的前驱节点。遍历结束后，把最小值节点的前驱的next指向最小值节点的next，然后释放最小值节点。

void DeleteMinNode(LinkList L) { if (L->next == NULL) { return; } LNode *pre = L; LNode *minPre = L; LNode *p = L->next; LNode *minNode = p; while (p != NULL) { if (p->data < minNode->data) { minNode = p; minPre = pre; } pre = p; p = p->next; } minPre->next = minNode->next; free(minNode); }

这个题目容易错的地方在于，不是记录最小节点的值就完事了，删除时还需要知道它的前驱，否则无法把链表重新接上。我把这个思路叫“双保险记录法”：边遍历边记录“当前最小节点”和“当前最小节点的前驱”，两者始终同步更新。另一个细节是，最小节点可能有多个，题目如果要求“只删除第一个最小值节点”，那判断条件就要用<而不是<=；如果要求删除所有最小值节点，就需要另外一种处理方式了。

4.5 多项式相加：结构体遇到链表的经典组合

多项式相加是第二章综合性很强的一道题。它把一个多项式定义为若干个项组成的线性表，每一项包含系数(coef)和指数(expn)。两个多项式相加，本质是合并两个按指数递减排列的有序链表。

实现思路比较直接：两个指针p和q分别指向两个多项式的首项，循环比较两者的指数。

• 如果p的指数大于q的指数，说明p这一项的结果里单独存在，直接把p节点复制到结果链表；
• 如果指数相等，系数相加，如果和不为0则插入结果链表，同时释放原来的两个节点；
• 如果指数小于，说明q这一项单独存在，把q节点复制到结果链表。

typedef struct PolyNode { float coef; int expn; struct PolyNode *next; } PolyNode, *PolyLinkList; PolyLinkList AddPoly(PolyLinkList A, PolyLinkList B) { PolyLinkList C = (PolyLinkList)malloc(sizeof(PolyNode)); C->next = NULL; PolyNode *p = A->next; PolyNode *q = B->next; PolyNode *r = C; while (p != NULL && q != NULL) { PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode)); if (p->expn == q->expn) { float sum = p->coef + q->coef; if (sum == 0) { p = p->next; q = q->next; free(s); continue; } s->coef = sum; s->expn = p->expn; p = p->next; q = q->next; } else if (p->expn > q->expn) { s->coef = p->coef; s->expn = p->expn; p = p->next; } else { s->coef = q->coef; s->expn = q->expn; q = q->next; } s->next = NULL; r->next = s; r = s; } while (p != NULL) { PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode)); s->coef = p->coef; s->expn = p->expn; s->next = NULL; r->next = s; r = s; p = p->next; } while (q != NULL) { PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode)); s->coef = q->coef; s->expn = q->expn; s->next = NULL; r->next = s; r = s; q = q->next; } return C; }

这道题真正考察的是“能不能把实际问题抽象成线性表的操作”。如果你能直接写出这个结构体和合并逻辑，说明你对链表已经有比较扎实的掌握。如果写不出来，就回到前面几道基础题先练手。多项式相加的变体还包括“多项式求值”“多项式乘法”，原理一样，后期可以延伸练习。

5. 算法题的边界条件与常见错误排查

5.1 空表、单节点、头节点：三个永远要先问的问题

我批改代码时有一个习惯：不管算法看起来多正确，先拿空表、单节点表、带头节点但无数据这三个特殊情况去测试。这三个测试用例能暴露大部分边界错误。

以删除链表中的值为x的节点为例。空表时，需要判断L->next == NULL，如果没判断，代码一运行就解引用空指针。单节点表时，如果该节点就是要删除的节点，删除后链表应该变成空表，也就是L->next = NULL，有些同学把这部分漏了。带头节点的链表在做插入操作时，头节点可以让“在第一个位置插入”和“在中间位置插入”的代码统一，但如果你的算法不依赖头节点，第一个数据节点和后继节点就需要分开处理。

但要注意的是，不要因为害怕边界条件就写出一堆冗余判断。好的代码应该是用统一逻辑覆盖特殊情况，而不是每种特殊情况单独写一个分支。比如带头节点的单链表删除节点，只要保证遍历时从头节点开始，用pre->next->data == x来判断，那么删除第一个数据节点和删除中间节点用的是同一段代码。

5.2 从越界到野指针：C语言做题常见的五个bug

这一节总结我在批改过程中遇到频率最高的五类C语言bug，按照出现概率排序：

第三类“指针悬挂”是最隐蔽的。有些操作系统在free后访问该地址不一定会立即崩溃，而是返回一个随机值，导致程序行为时好时坏。这个问题排查起来很头疼，只能靠规范编程来避免。我的原则是：free一个指针后，要么马上置空，要么保证它再也不会被访问。

5.3 如何验证你的算法是对的：测试用例设计的三个层次

很多同学写完算法后不知道怎么验证正确性，就随便输入几个数据跑一遍，感觉没报错就算过了。这种做法风险很大，因为很多隐藏bug在特定输入下才会暴露。

我建议采用三个层次的测试：

第一层是“功能测试”，验证算法能否完成基本功能。比如删除所有值为x的数据，输入[1, 2, 3]，删除2，期望得到[1, 3]。这一层能发现大部分逻辑错误。

第二层是“边界测试”，使用最小规模数据。空表、单节点、两个节点、最大值、最小值、所有元素相同、没有要删除的元素、所有元素都要删除。这些用例能发现边界处理是否完善。

第三层是“压力测试”，构造大规模数据。比如线性表长度取到几万，把元素随机打乱，再对比你的算法结果和暴力解法结果是否一致。对于链表，可以随机插入几万个节点，测试插入、删除、查找的性能和正确性。这一层在上机考试前做一次，能极大增强信心。

从经验来看，能把第二层测试做全的人，代码质量已经超过大多数同学了。第三层测试主要是自我加压，适合冲刺高分的人。

6. 顺序表和链表的综合对比：从课后题到期末考

6.1 一张表说清两种存储结构的所有区别

第二章学完之后，我建议你亲手整理一张对比表。这里给出我的版本，你可以在此基础上补充：

这张表是第二章知识的浓缩。期末复习时，建议把表右侧再补一列“教材例题中的体现”，比如顺序表插入在哪个函数里演示过，链表删除在哪个函数里演示过。这样就完成了从知识点到代码的映射。

6.2 选择恐惧症怎么治：先看操作频率再看数据规模

面试和考试里常见的一类题是“给你一个场景，你选顺序表还是链表”。这类题其实有套路。

第一步看主要操作是什么。如果主要操作是按下标随机访问元素，比如“取得第i个位置的元素”，那顺序表是明显优势。如果主要操作是频繁在中间插入和删除，比如“维护一个不断变化的任务队列”，那链表更合适。

第二步看数据规模。数据量小（比如几百个元素），两者性能差异微乎其微，用顺序表即可，因为代码简单、可读性好。数据量大且动态增长，无法预估上限，那链表更合适，否则顺序表频繁扩容反而浪费时间。

第三步看是否需要稳定的存储地址。顺序表扩容时元素会整体搬家，原来的指针全部失效；链表节点稳定存在，只要不删除，地址不会变化。

这三步想清楚，大部分选型题都不会出错。

6.3 “快慢指针”这个思想从第二章就开始埋伏了

第二章有一道题是“找链表中间节点”，这个题的最优解用到了快慢指针：一个指针每次走两步，另一个每次走一步，快指针到末尾时，慢指针刚好指向中间节点。

这个思想在第二章只是一个锻炼，但后续会多次出现。判断链表是否有环时，快慢指针是经典解法；找链表倒数第k个节点时，同样用快慢指针，先让快指针先走k步，然后两个指针同步前进。理解快慢指针的本质是“不同速度的遍历产生相对位移”，在后面的章节里你会频繁用到。

我建议在第二章就把快慢指针的两种模式练熟：一是“快走两步、慢走一步”找中点；二是“先走k步再同步走”找倒数第k个节点。这两种模式代码量都很小，但面试和考试中出镜率很高。

6.4 我自己刷第二章时踩过的坑

文章最后，按惯例分享几个我当初刷这章时踩过的坑。

第一个坑是“眼高手低”。我当时觉得顺序表的题简单，直接在草稿纸上画画逻辑就过了，没有真正上机写代码。结果第一次上机做“删除所有值为x的元素”时，写出来的代码在x连续出现时逻辑就出错了。后来我养成了一个习惯：不管是多简单的算法题，都要亲自写一遍代码，并且用测试用例跑一遍。

第二个坑是“死磕一道题”。遇到“多项式相加”这种综合性较强的题时，我花了一整个晚上硬磕，导致效率很低。后来我改变了策略，一道题超过一个小时还理不清思路，就先放下，回头把前面链表的基础操作重新练一遍，第二天再回来做，往往很快就通了。这个策略后来一直用到考研复习结束。

第三个坑是“忘记看输出的中间状态”。调试链表代码时，很多人习惯只盯着最终结果对不对。但我建议你在关键位置加printf，把每一步的指针指向打出来。比如反转单链表，每经过一个节点就打印一次当前prev、curr、next的地址和数据，能帮助你把指针变化过程可视化，快速定位断链的位置。

第四个坑是“直接抄答案”。教材附录和网上流传的答案里有一些代码风格很老，甚至存在小错误。我建议把答案当作参考，不要直接背，一定要自己推导一遍。考试和面试时，考官更看重你能否清晰地解释每一步的逻辑，而不是你是否背过标准答案。

这些经验虽然看起来琐碎，但都是实打实趟出来的。数据结构的学习没有捷径，第二章作为基础中的基础，值得你多花时间把每道题都吃透。后面几章的很多代码，你会发现都只是在这一章的基础上换了一层皮而已。