企业官网建设流程全解析

一元多项式的乘法与加法运算，是我在在线判题平台上反复见过的一道经典题。第一次写的时候，我花了不到半小时就把加法写完，结果挂在乘法上——不是算法写错，而是乘法产生的新项没有保持指数递减，输出格式也不符合要求。这道题表面上是“两个多项式相加、相乘”，其实考的是三件事：链表的插入删除、有序结构的合并、边界条件处理。我见过不少基础不错的同学卡在零多项式和空格上，所以决定把完整的实现思路和踩坑记录整理出来，给正在刷链表题的人一个可以复现的参考。

1. 题目到底在考什么：读题阶段最容易忽略的三件事

很多题解上来就贴链表代码，但真正让你交不上去的，往往不是链表本身，而是对输入输出规则的理解。先把规则拆开，再谈算法，顺序不要反。

1.1 输入不是多项式本身，而是“项数 + 系数指数交替”

题目给的输入格式是两行，每行第一个整数表示多项式的项数，之后跟着若干对“系数 指数”。例如：

4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1

第一行表示第一个多项式有 4 项，分别是 3x^4、-5x^2、6x、-2；第二行表示第二个多项式有 3 项，分别是 5x^20、-7x^4、3x。这里指数是递减给出的，这个顺序很关键。

我见过有人把“项数”当成指数最大值，直接开数组，结果整个程序跑偏。正确的做法是：先读项数 n，再循环 n 次，每次读一对“系数 指数”。如果系数为 0，直接丢弃这一项，不存入链表。虽然标准测试数据里通常不会出现系数为 0 的项，但处理一下没有坏处，反而让程序更稳。

1.2 输出要求指数递减，而且结果要先合并同类项

输出分两行：第一行是乘法结果，第二行是加法结果。每个结果都要满足两个硬性要求：

• 指数必须按从大到小排列；
• 同指数的项必须合并，不能出现“两个指数相同的项分别输出”的情况。

这两个要求决定了你选择的存储结构和插入逻辑。如果你的链表是无序的，或者插入新项时不去合并同指数项，哪怕算法算对了，输出也是错的。我最初踩的坑就是这里：乘法用两重循环算完所有乘积项之后，没有合并直接输出，结果被判 WA。

1.3 零多项式的定义与处理

如果某个多项式没有任何项，也就是零多项式，输出规则是单独一行0 0。注意是“0 空格 0”，后面不要跟多余的冒号、括号，也不要输出空行。

零多项式不仅可能出现在输入里，也可能在运算过程中产生。比如两个多项式相加后所有系数抵消，乘积中同类项合并后全部抵消。我见过有人写了很多代码，最后却忘了处理“运算结果为空链表”的情况，一输出就变成空白行。这个细节在后面会专门讲。

2. 链表还是数组：两种方案的取舍，以及我最终选择的理由

这个问题几乎每道数据结构题都会遇到。我的结论是：这道题用链表做最稳，但不代表数组法一无是处。关键是搞清楚各自适用条件。

2.1 数组下标法的思路与局限性

如果采用数组法，可以开一个足够大的数组coef[maxExp]，把系数存到指数对应的下标里。加法直接对应下标相加；乘法用两重循环累加乘积。这种写法在指数范围比较小的时候非常舒服，代码短，也不容易出指针问题。

但它的局限性也很明显：

• 题目通常不会明确给出指数上界，你不知道该开多大数组；
• 如果指数能到十万、百万，数组法要么浪费空间，要么直接越界；
• 输出前还要把数组从头扫到尾，收集“系数非零”的下标，再逆序输出，代码并不比链表少多少。

指数范围问题不是编出来的。我见过一份用数组写的题解，他假设指数不超过 1000，结果遇到一个指数为 2000 的测试点就崩了。所以，如果你不确定数据范围，链表是更安全的选择。

2.2 单链表节点设计与带头结点的好处

用链表实现时，节点结构很简单：

typedef struct Node { int coef; int exp; struct Node *next; } Node;

我习惯给链表加一个不存数据的头结点，也就是head->next指向第一个实际节点。空链表时head->next == NULL。带头结点有三个好处：

1. 空表和普通表的处理逻辑完全统一，不需要写if (head == NULL)这种分支；
2. 在头部插入节点时，不需要修改外部指针变量；
3. 删除节点时，只需要知道前驱节点，操作起来很顺手。

有人喜欢用“指向指针的指针”来处理头部插入，但带头结点后，这个问题自然消失了。

2.3 什么情况下可以无脑用数组，什么情况下必须上链表

我的判断标准很简单：

• 如果题目明确给出指数范围，比如“指数不超过 100”，直接用数组，又快又好；
• 如果题目没有给范围，或者多项式项数较多、指数分布稀疏，就用链表；
• 如果这道题就是链表专题训练，那不要犹豫，用链表，因为你练的就是这个。

另外，链表方案的运行时间虽然不是最优，但对这道题完全够。两个多项式项数加起来不过几十项，乘法双重循环最多几千次操作，链表插入的常数开销完全可以接受。

3. 加法实现：一次扫描完成同类项合并，关键是处理好“系数抵消”

加法是这道题里最简单但最容易写糙的部分。很多人写出一个能算出结果的加法，却没有处理“系数相加为 0”的情况，最后在特殊数据上翻车。

3.1 归并式加法：两个有序链表怎么合并

因为输入的两个多项式本身已经按指数递减排列，所以加法可以像归并排序一样，用两个指针各自往后扫，每次比较当前节点的指数：

• 指数相同：把系数相加，合并成新节点；
• 左边指数大：把左边节点复制到结果链表；
• 右边指数大：把右边节点复制到结果链表。

这个过程有一点像拉链：两个有序序列合并成一个有序序列，时间复杂度是 O(m+n)，m 和 n 分别是两个多项式的项数。

一个容易忽略的点是，这里必须“复制”节点，而不是直接把原链表的节点挂到结果上。原因是这道题做完加法之后还要做乘法，如果你把 A 或 B 的节点直接搬走，会让原链表被破坏，后面的乘法就全错了。复制节点虽然多写几行代码，但逻辑上安全很多。

3.2 系数相加为 0 时，必须删除这一项

假设 A 里有一项-3 2，B 里有一项3 2，两者指数都为 2，系数相加等于 0。这时在结果链表中不应该出现任何记录，连“系数 0 指数 2”都不能留。否则输出里会出现一个系数为 0 的多余项，直接 WA。

处理方式很直接：只有在合并后的系数不为 0 时才创建新节点；如果不为 0，就正常插入；如果为 0，直接跳过去。

3.3 完整加法代码

Node *addPoly(Node *A, Node *B) { Node *p = A->next; Node *q = B->next; Node *head = createList(); Node *tail = head; while (p && q) { if (p->exp == q->exp) { int sum = p->coef + q->coef; if (sum != 0) { tail->next = createNode(sum, p->exp); tail = tail->next; } p = p->next; q = q->next; } else if (p->exp > q->exp) { tail->next = createNode(p->coef, p->exp); tail = tail->next; p = p->next; } else { tail->next = createNode(q->coef, q->exp); tail = tail->next; q = q->next; } } while (p) { tail->next = createNode(p->coef, p->exp); tail = tail->next; p = p->next; } while (q) { tail->next = createNode(q->coef, q->exp); tail = tail->next; q = q->next; } return head; }

辅助函数createNode负责分配内存并初始化节点，createList创建带头结点的空链表。这两个函数我建议单独写，后面乘法也要用。

这个加法函数还有一个隐藏的好处：结果天然就是指数递减的，不需要额外排序。因为每次比较后总是先把指数较大的节点接入结果链表，所以结果链表的顺序自然满足题目要求。

4. 乘法实现：逐项相乘再有序插入，踩过排序坑之后我换成了这种写法

乘法是本体的重头戏。常见的错误包括：忘记合并同类项、结果没有排序、把节点挂错导致死循环。我推荐一种经过验证的写法：双重循环逐项相乘，每产生一个乘积项，就按指数递减的位置插入结果链表，插入时顺便完成同类项合并。

4.1 乘法的数学本质：每一项乘整体，再累加

设多项式 A 有 m 项，多项式 B 有 n 项。从数学上讲：

A × B = a1 × B + a2 × B + ... + am × B

所以代码上就是双重循环：外层遍历 A 的每一项，内层遍历 B 的每一项。每一项相乘得到新的系数p->coef * q->coef，新的指数p->exp + q->exp。

这个新项不能无脑追加到链表尾部，因为它的指数可能大于或小于结果链表中已有的项，必须插到合适的位置，才能保证结果始终按指数递减。

4.2 有序插入函数：维护结果链表按指数递减

有序插入的逻辑如下：

1. 从结果链表头结点开始，用两个指针pre和cur找插入位置；
2. 循环条件是cur 存在 且 cur->exp > 新指数，也就是跳过所有指数比新项大的节点；
3. 循环结束后，如果cur的指数正好等于新指数，说明遇到同类项，直接累加系数；
4. 累加后如果系数为 0，删除该节点；
5. 如果没找到同类项，就把新项插在pre和cur之间。

因为插入是在遍历过程中完成的，所以不需要单独再做一次排序。这样写虽然每一步插入都要从头扫描，最坏复杂度偏高，但本题数据量小，代码简洁远比微优化重要。

void insertNode(Node *head, int coef, int exp) { Node *pre = head; Node *cur = head->next; while (cur && cur->exp > exp) { pre = cur; cur = cur->next; } if (cur && cur->exp == exp) { cur->coef += coef; if (cur->coef == 0) { pre->next = cur->next; free(cur); } } else { Node *node = createNode(coef, exp); node->next = cur; pre->next = node; } }

这里有个值得注意的细节：插入新项时，系数如果为 0，理论上不应该插入。所以调用insertNode之前可以先判断coef != 0。不过即使传入 0 系数，上面的逻辑也能把它插入，只是不理想。我习惯在调用处判断。

4.3 乘法完整代码与复杂度分析

Node *multiplyPoly(Node *A, Node *B) { Node *head = createList(); for (Node *p = A->next; p != NULL; p = p->next) { for (Node *q = B->next; q != NULL; q = q->next) { int coef = p->coef * q->coef; int exp = p->exp + q->exp; if (coef == 0) { continue; } insertNode(head, coef, exp); } } return head; }

复杂度分两层：最外层双重循环是 O(mn)，内层每个乘积项插入结果链表时需要扫描，最坏情况每一步都要扫到链表末尾，所以整体最坏是 O(mn × (m+n))。对这道题来说，m 和 n 最多也就是几十，完全不是问题。

但是要注意：如果测试数据里多项式项数特别大，这个写法就可能超时。在那种情况下应该先把每个乘积项存到临时数组里，最后统一排序再合并；或者用另一种思路：每用一个项乘完整个 B，得到一个临时有序链表，再与结果链表做一次归并合并。这类优化我暂时不展开，因为基础题的常规数据根本用不上。

5. 判题死角与自测方案：把零多项式、同类项合并、空格全测一遍

这道题出错的大头不是算法，而是边界和格式。我整理了一份自测清单，提交前照着跑一遍，能帮你省下大量试错时间。

5.1 容易翻车的输入形态

第一种是“项数为 0”的输入。某些测试点会用一行0表示零多项式。读入时要正常处理：读完 0 之后不创建任何节点，链表为空。

第二种是输入中混入系数为 0 的项，例如1 0 3。虽然数学上这样写不标准，但判题数据里未必不会出现。让我更稳妥的做法是：读项时只要发现系数为 0，就跳过，不建节点。

第三种是运算结果恰好为零多项式。比如乘法结果每一项最终都与别的项抵消，或者一个多项式本身就是零多项式。这时输出必须是一行0 0。

5.2 自测用例表：照着测一遍心里就有底了

我建议你仿照上面自己手算几个用例，比如用简单的(x+1)和(x-1)，然后把程序输出打印出来逐项核对。不要只在脑子里想，一定动手跑。

5.3 常见判题结果到底在提示什么

• 返回 WA，且你的输出看起来数字都对：大概率是输出格式问题，比如最后多了空格、少了空格、输出顺序反了；
• 返回 WA，且数字不对：先检查同类项是否合并，再检查链表是否按指数递减；
• 返回 RE 或段错误：多半是指针操作出了问题，常见原因是free之后还继续使用那个节点，或者循环里指针没有前进；
• 返回 PE 格式错误：优先检查0 0这种零多项式输出，检查每项之间的空格。

这里给一个说法：输出格式严格到什么程度？就是每行最后一个数字之后不能有空格，换行前不多余；两项之间恰好一个空格。我第一版就是最后一项后面多打了一个空格，被判了格式错误。

6. 提交前再检查一遍：我常用的三个小技巧

链表题写起来不难，但小毛病特别多。我总结了三个平时自己一定会做的检查步骤。

6.1 单独写一个打印函数，随时观察中间过程

调试链表题，最直接的辅助工具就是一个能完整输出链表的函数。我在写主流算法之前，会先把printPoly写出来，每次合并完立即打印。一旦某个测试点不对，马上能定位是在加法的哪一步出了问题，还是乘法插入的时候出了问题。

注意：调试时可以在每个关键节点后加printf，但提交前一定要把调试输出全部删掉。我就有过一次忘记删调试输出，结果整版判 WA，白白浪费一次提交机会。

6.2 检查插入和删除时前驱指针是否维护正确

链表题 80% 的指针错误都出在“插入节点时没有正确维护前驱节点的 next”。我的经验是：每次写完插入函数，先在心里跑一个小用例：

链表：head -> (3,4) -> (2,0) 插入 (5,2)，保证结果：head -> (3,4) -> (5,2) -> (2,0)

如果你能把这个用例跑对，链表的插入和删除基本功就稳了。不要直接拿复杂数据测试，小用例反而更好定位。

6.3 提交之前把所有临时变量、释放函数再读一遍

我的习惯是写destroyList函数，哪怕在线判题不检查内存泄漏，也把节点全部释放。这样一方面养成好习惯，另一方面，如果你在一个函数里提前释放了某个节点，后续再访问它，调试器很容易就能发现错误位置。

释放顺序也有讲究：先保存next，再free当前节点。否则free之后你拿不到next，就成了经典的“悬空指针错误”。

如果让我重写一次这道题，我会把insertNode写得比主函数还仔细，因为一切错误都发生在插入和删除里。加法是一次归并，乘法是循环插入，两者共用同一个有序链表结构。想通这一点，这一题就不再是“会不会写链表”的问题，而是“能不能保证每一步操作都维护好链表性质”的问题。