不知道有多少人和我一样第一次在PTA拼题A上刷到这道“7-2 一元多项式的乘法与加法运算”的时候心里想的是这不就是合并同类项吗初中生都会。然后自信满满地写了个数组版一提交Runtime Error或者Wrong Answer直接被20分的题教做人。这道题放在数据结构课程里考查的从来不是“你会不会算多项式”而是“你会不会用线性结构去组织数据并在组织的过程中把边界条件处理干净”。尤其是链表版本稍不留神就踩进空指针、零多项式、系数抵消的坑里。这篇东西我不打算给你抄一份标准答案就完事而是把这道题从考点拆解、数据结构选型、加法乘法实现细节、输出格式的隐藏要求到完整的可运行代码和测试用例全部过一遍。无论你是正在学《数据结构》的本科生还是在准备考研机试、找工作笔试需要巩固链表操作的读者这篇应该都能让你把这20分拿得明明白白。1. 这道20分题的考点拆解别急着写代码先看懂题目在考什么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。输出则是两行第一行是乘积结果第二行是求和结果15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0注意看输出里没有任何多余的说明文字没有“Result is”就是纯粹的一串数。很多同学第一次写的时候会把“系数 指数”写反或者多个空格少个空格这些都是扣分点。后面我会专门拿出一节来梳理输出格式的坑。1.2 数据结构选型链表还是数组这道题最经典的做法有两种数组和链表。很多学校的数据结构课程讲义里这道题的标准答案是用带头结点的单链表实现。为什么因为这道题出现在“线性表”章节之后本质上就是训练你对链表这种动态存储结构的掌握程度。用数组做当然可以做甚至代码写起来更短。核心就是开一个足够大的数组以指数为下标系数为值直接累加。但问题来了数组的大小需要预先确定万一指数很大怎么办题目如果出现x^1000这种项你得开出1001个元素如果出现x^1000000内存就有点尴尬了。数组无法体现“动态分配、按需存储”的思想而这恰恰是链表存在的意义。这题叫“数据结构与算法”课程题老师希望你练的是链表操作——创建、插入、删除、遍历、合并。你用数组做哪怕AC了课程设计的分数也未必高。所以这篇博文我会以链表为主线来讲。用链表做这道题你实际训练的是以下几项核心能力带头结点链表的创建与遍历按指数有序插入的算法两个链表合并加法时的指针移动策略两个链表逐项相乘后再合并同类项的运算组织动态内存的申请与释放。这些能力在后面的“多项式运算”“稀疏矩阵”“一元多项式求导”等题目里都会反复用到。把这道题吃透等于把链表的核心操作过了一遍。1.3 为什么带头结点的单链表写起来最顺手很多教材在讲链表时会区分“带头结点”和“不带头结点”两种写法。这道题我强烈建议你用带头结点的方式。原因很简单头结点不存数据它的作用是把“插入第一个节点”和“插入后面的节点”统一成同一种操作。比如要在链表尾部追加一个节点带头结点时无论链表当前是否为空逻辑都是“从头结点开始找到最后一个节点然后接上新节点”。不带头结点时你每次都得判断“链表是不是空的”如果不是才走找尾结点的逻辑多一层分支代码容易乱。创建带头结点的空链表初始化的写法是typedef struct PolyNode *Polynomial; struct PolyNode { int coef; // 系数 int expon; // 指数 Polynomial link; // 指向下一项 }; Polynomial createEmptyPoly() { Polynomial P (Polynomial)malloc(sizeof(struct PolyNode)); P-link NULL; return P; }头结点本身的coef和expon可以随便初始化不影响后面的运算逻辑。你只需要记住这个节点是“哨兵”从它后面的第一个节点开始才是真正的多项式项。2. 多项式加法两个指针并行扫描指数大的先走2.1 加法的核心逻辑加法是这道题里相对简单的部分但简单不等于可以掉以轻心。两个多项式相加的规则是指数相同的项系数相加指数不同的项直接照抄。用链表实现时通常的做法是用两个指针分别指向两个多项式的第一个有效节点然后比较它们当前指数的大小如果第一项的指数大于第二项的指数说明第一项在结果里应该排在前面把第一项复制到结果链表指针A后移如果第一项的指数小于第二项的指数说明第二项应该排在前面把第二项复制到结果链表指针B后移如果两项指数相等则把系数相加。如果相加后的系数不为0就生成一个新节点挂到结果链表如果系数为0这一项就消失了两个指针都后移。这个思路本质上就是“归并排序”的归并阶段那种双指针扫描。理解这一点后面学归并、合并有序链表时都会觉得顺。对应代码实现Polynomial polyAdd(Polynomial P1, Polynomial P2) { Polynomial front, rear, temp; rear (Polynomial)malloc(sizeof(struct PolyNode)); front rear; // 用front记住结果链表的头结点位置 P1 P1-link; P2 P2-link; while (P1 P2) { if (P1-expon P2-expon) { attach(P1-coef, P1-expon, rear); P1 P1-link; } else if (P1-expon P2-expon) { attach(P2-coef, P2-expon, rear); P2 P2-link; } else { int sum P1-coef P2-coef; if (sum ! 0) { attach(sum, P1-expon, rear); } P1 P1-link; P2 P2-link; } } // 剩余项直接接到结果后面 while (P1) { attach(P1-coef, P1-expon, rear); P1 P1-link; } while (P2) { attach(P2-coef, P2-expon, rear); P2 P2-link; } rear-link NULL; temp front; front front-link; // 跳过头结点 free(temp); // 释放头结点 return front; }这里有一个很关键的设计attach函数。它的作用是在链表末尾插入一个新节点。由于我们每次都要更新链表的尾指针rear所以attach接收的是rear的指针的指针。这是C语言里常见的一个细节——你需要修改调用者那边保存的尾指针值而C语言函数传值所以必须传二级指针才能让rear在函数内被更新后调用者能看到变化。2.2 attach尾插法的写法与细节attach函数的实现void attach(int coef, int expon, Polynomial *pRear) { Polynomial P (Polynomial)malloc(sizeof(struct PolyNode)); P-coef coef; P-expon expon; P-link NULL; (*pRear)-link P; *pRear P; }注意*pRear在进入函数时指向当前链表的最后一个节点。我们让它的link指向新节点然后更新*pRear为新的节点。这样调用结束后外界的rear就自动指向新链表的尾巴了。如果不传二级指针而是传Polynomial rear那么函数内部修改rear的值不会影响外面。这是一个经典C语言陷阱。很多同学链表写不好一半的bug出在“为什么我的尾指针没有移动”这种问题上。这里一定要想明白你修改的是指针变量的值还是指针指向的内存内容(*pRear)-link P修改的是“尾节点指向的下一个节点”这是内存内容不传二级指针也能改但是*pRear P修改的是“尾指针变量本身的值”这就必须二级指针才行。2.3 加法里容易忽略的边界情况加法部分有几个边界情况值得单独拎出来说。第一个情况是系数抵消。假设P1里有3 4P2里有-3 4两者指数相同系数相加等于0这一项不能在结果里出现。如果你把系数为0的节点也插入结果链表你的输出格式就错了——会输出0 4这一项这在逻辑上是错的因为0x^4等于0不是多项式的一项。第二个情况是空多项式。题目输入里给出的项数可能包含0吗实际上PTA原题的正则约束里输入的都是项数至少为1的情况。但你自己测试时应该考虑如果其中一个多项式只有一项、甚至都只有一项的情况。链表实现里只要有一个多项式为空也就是head-link为NULL加法就会全部落到“剩余项直接接上”的逻辑里。第三个情况是两个多项式完全一样加完之后系数变成原来的两倍。这个看起来没问题但要注意如果你在加法过程中修改了原链表节点的值比如直接P1-coef P2-coef而不新建节点就会破坏原数据。虽然这道题只要求输出不改原数据也能过但养成“运算不修改输入数据”的习惯是好的因为后面的复杂题目往往会要求你保留原多项式供多次使用。3. 多项式乘法先构造再合并别边乘边插3.1 两层循环逐项相乘多项式乘法的规则是第一个多项式的每一项分别乘以第二个多项式的每一项把得到的乘积项收集起来再把指数相同的项合并。用链表实现时最直接的方式就是两层循环外层遍历P1的每一项内层遍历P2的每一项让coef P1-coef * P2-coefexpon P1-expon P2-expon把结果用一个临时结果链表收集。这个过程可以用一个间接的思路理解乘法展开就是在做“每一项都乘一遍”和手算多项式时一个一个相乘再合并的过程一模一样。比如(3x^4 - 5x^2 6x - 2)乘以(5x^20 - 7x^4 3x)你先用3x^4去乘第二个多项式得到15x^24 - 21x^8 9x^5再用-5x^2去乘得到-25x^22 35x^6 - 15x^3依次类推。所有项产生之后把指数相同的项系数加起来。一种比较清晰的实现是先用P1的第一项乘以P2的所有项构造出一个“种子结果链表”然后继续用P1的第二项、第三项……去乘P2每乘出一项就插入结果链表的合适位置如果指数相同则合并系数。这种写法的好处是结果链表始终是“有序且无同类项”的最后不需要再做一次独立的合并操作。另一种实现方式是把所有乘积项放进一个临时链表不管重不重复结束后统一排序、合并同类项。这种方式代码简单但要多一次排序和遍历合并。考虑到这题数据量小怎么都无所谓但从算法素养的角度第一种“边乘边插入有序链表”的写法更优雅也更贴合“在有序链表中插入节点”这个考点。3.2 在有序链表中插入与合并我采用的方案是先构造空结果链表P然后对P1的每一项遍历P2的每一项把乘积结果通过一个专门的insertPoly函数插入到结果链表P中。insertPoly的内部逻辑是从结果链表头开始找到第一个指数小于等于当前项指数的位置如果当前位置的指数等于当前项的指数就把系数相加如果相加后系数为0删除该节点如果当前位置的指数小于当前项的指数就把新节点插到它前面。需要特别注意的是这个“寻找插入位置”的过程必须维护一个前驱指针prev。因为单链表只能往后走你要在某个节点之前插入就必须记录它的前一个节点。插入的核心操作是newNode-link prev-link; prev-link newNode。但这里有一个比插入更隐蔽的问题合并同类项后系数如果变成0需要删除节点。删除节点同样需要前驱指针。而且删除之后你不能继续用原来的当前节点指针继续走得回到前驱节点继续判断。我见过很多人在这一步翻车写出来的代码在“结果多项式有抵消项”时出错。等下在“完整代码实现”部分我会给出对应代码。3.3 乘法的时间复杂度和优化讨论直接用两层循环有序插入时间复杂度最坏是O(nmLen)其中n、m分别是两个多项式的项数Len是结果链表的长度。在题目20分题的数据范围内这个复杂度完全够用。n和m一般不超过几十Len最多是n*m所以最坏情况下也就是几十乘几十CPU毫无压力。但如果你想显摆一下自己的算法功底可以提一下更优的思路先用O(nm)算出所有乘积项并放在一个数组中或临时链表里然后排序O(nm log(nm))再按顺序合并同类项。当n、m比较大的时候这种“先收集再排序”的方式比“边乘边插入”要更稳定。因为边乘边插入需要一次次地从链表头部往下找插入位置最坏情况是O(k)的查找而k是结果链表长度整体就会退化到O(nm*k)。我自己的建议是在考场或机试环境下代码写对比代码写快更重要。选你最有把握、最容易调通的思路。如果你对链表的插入删除已经炉火纯青那就用边乘边插如果你觉得把握不大就先把乘积项全部挂到临时链表最后调用一个“排序合并”函数统一处理。考试是为了拿分不是为了耍帅。4. 输出格式这道题一半的坑都在输出上4.1 输出要求里藏着哪些细节再回头看看题目要求的输出形式。以加法的结果为例输出是5 20 -4 4 -5 2 9 1 -2 0这里每个“系数 指数”对之间用空格隔开但行末不能有额外空格。很多同学在写循环输出时习惯在每项后面打一个空格然后最后一项多了个空格这在PTA上就是Presentation Error或者Wrong Answer。处理方式有两种方式一判断当前节点是不是第一个节点不是的话先输出一个空格再输出系数指数。void printPoly(Polynomial P) { int flag 0; if (!P) { printf(0 0\n); return; } while (P) { if (!flag) { printf(%d %d, P-coef, P-expon); flag 1; } else { printf( %d %d, P-coef, P-expon); } P P-link; } printf(\n); }方式二先输出第一个节点之后每个节点前面都补一个空格。效果一样。我个人习惯用方式一因为逻辑上更统一不用单独拉出第一个节点。4.2 零多项式的输出是个大坑如果两个多项式相乘或相加的结果是零多项式怎么输出这个很多人不知道。题目明确要求如果结果是零多项式输出0 0。这里的“零多项式”是指所有项的系数都是0或者说结果里没有任何有效项。比如x (-x)结果是0。你不能什么都不输出必须输出一行0 0。在数学上“0 0”不是一个严格意义的多项式项但这就是本题的约定——用“系数0、指数0”来表示零多项式。原因很简单输出格式必须保持两行都有内容否则没法解析。所以你的打印函数必须判断链表是否为空。如果结果链表是空链表直接输出0 0\n。这里还要注意一个逻辑联动当你做合并同类项时如果某个节点的系数相加后为0你要把该节点从链表中删除。如果删除后链表变空了就说明结果多项式是零多项式。有些人的代码在系数抵消时只把系数置0而保留节点最后打印的时候虽然会输出0 指数这不符合题目要求的0 0格式。所以正确处理是系数为0就删节点而不是留下一个系数为0的脏节点。4.3 关于指数为0和系数为1/负数的输出多项式里如果有一项的指数是0意味着这是常数项。输出时不需要特殊处理就正常输出“系数 0”。比如5x^0输出为5 0。这个在题目的样例里出现过-2 0就是常数项-2。系数为1的时候正常人手写多项式会写作x^3而不是1x^3系数为-1时写作-x^3。但这道题并不要求你按照数学规范化简输出直接输出1 3也是对的。我见过有些同学在这个地方画蛇添足试图判断系数为1就不输出系数结果数据格式反而错了。切记PTA程序题是按格式判分的你和裁判之间唯一的交流就是那几行数字千万别用自己的“数学直觉”去猜输出格式一切以题目描述为准。系数为负值时直接打印负数即可比如-5 2表示-5x^2。题目没有要求你处理符号直接printf(%d, coef)就完事。4.4 指数降序排列的保证输出要求按指数降序排列。如果你的结果链表始终是有序的——比如用“边乘边插入有序链表”的方式那打印时自然就是降序。如果你用了“临时链表收集最后合并”的方式那么合并前必须先排序。这里强烈建议不要把排序和合并分成两个函数而是先用某种方法让链表有序然后单遍扫描合并同类项。一种实现思路是先把临时链表用冒泡或插入排序整理成降序再一次遍历把相邻的同类项合并。因为排好序之后指数相同的项必然是相邻的一次遍历就能合并完。如果你在排序之前合并那还得用双重循环逐个找相同的项白白增加复杂度。5. 完整代码与测试按这个模板写稳过5.1 完整可运行的C语言实现下面这份代码是我实际调试通过的版本用带头结点单链表实现乘法采用“边乘边插入有序链表”的方式。里面包含了完整的创建、插入、相加、相乘、打印、释放内存函数。我加了比较详细的注释你把它完整复制到本地用gcc编译运行再对照题目样例应当能直接通过。#include stdio.h #include stdlib.h typedef struct PolyNode *Polynomial; struct PolyNode { int coef; int expon; Polynomial link; }; // 在链表末尾接一个新节点pRear为尾指针的指针 void attach(int coef, int expon, Polynomial *pRear) { Polynomial P (Polynomial)malloc(sizeof(struct PolyNode)); P-coef coef; P-expon expon; P-link NULL; (*pRear)-link P; *pRear P; } // 读取多项式 Polynomial readPoly() { int n, coef, expon; scanf(%d, n); Polynomial front (Polynomial)malloc(sizeof(struct PolyNode)); Polynomial rear front; front-link NULL; for (int i 0; i n; i) { scanf(%d %d, coef, expon); attach(coef, expon, rear); } return front; } // 在有序链表P中插入一项保持指数降序。若指数相同则合并系数。 void insertPoly(Polynomial P, int coef, int expon) { Polynomial prev P; // 前驱指针初始指向头结点 Polynomial curr P-link; // 当前节点 // 找到插入位置curr为空或curr的指数小于等于待插入指数 while (curr curr-expon expon) { prev curr; curr curr-link; } if (curr curr-expon expon) { // 指数相同合并系数 curr-coef coef; if (curr-coef 0) { // 系数抵消删除当前节点 prev-link curr-link; free(curr); } } else { // 指数不同插入新节点到prev之后 Polynomial newNode (Polynomial)malloc(sizeof(struct PolyNode)); newNode-coef coef; newNode-expon expon; newNode-link curr; prev-link newNode; } } // 多项式加法 Polynomial polyAdd(Polynomial P1, Polynomial P2) { P1 P1-link; P2 P2-link; Polynomial front (Polynomial)malloc(sizeof(struct PolyNode)); Polynomial rear front; front-link NULL; while (P1 P2) { if (P1-expon P2-expon) { attach(P1-coef, P1-expon, rear); P1 P1-link; } else if (P1-expon P2-expon) { attach(P2-coef, P2-expon, rear); P2 P2-link; } else { int sum P1-coef P2-coef; if (sum ! 0) { attach(sum, P1-expon, rear); } P1 P1-link; P2 P2-link; } } while (P1) { attach(P1-coef, P1-expon, rear); P1 P1-link; } while (P2) { attach(P2-coef, P2-expon, rear); P2 P2-link; } rear-link NULL; return front; } // 多项式乘法 Polynomial polyMult(Polynomial P1, Polynomial P2) { P1 P1-link; P2 P2-link; Polynomial front (Polynomial)malloc(sizeof(struct PolyNode)); front-link NULL; if (!P1 || !P2) { return front; // 有零多项式时结果为空链表 } for (Polynomial p P1; p; p p-link) { for (Polynomial q P2; q; q q-link) { int coef p-coef * q-coef; int expon p-expon q-expon; insertPoly(front, coef, expon); } } return front; } // 打印多项式 void printPoly(Polynomial P) { P P-link; if (!P) { printf(0 0\n); return; } int flag 0; while (P) { if (!flag) { printf(%d %d, P-coef, P-expon); flag 1; } else { printf( %d %d, P-coef, P-expon); } P P-link; } printf(\n); } int main() { Polynomial P1 readPoly(); Polynomial P2 readPoly(); Polynomial product polyMult(P1, P2); printPoly(product); Polynomial sum polyAdd(P1, P2); printPoly(sum); return 0; }5.2 测试用例设计写完代码之后一定要自己造几组测试数据。我列几个必测的用例每个都踩到过不同的坑。测试用例1标准样例4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1预期输出15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0测试用例2指数相同、系数抵消第一个多项式2x 1第二个多项式-2x 1也就是2 2 1 1 0 1 2 -2 1 1 1 0加法结果应该为常数2即输出2 0。乘法结果呢计算一下(2x1)(-2x1) -4x^2 2x - 2x 1 -4x^2 1输出-4 2 1 0。这个用例能检查你的insertPoly在同指数合并后系数抵消的删除逻辑。测试用例3结果为0第一个多项式x第二个多项式-x即1 1 1 1 -1 1加法结果为零多项式输出一行0 0。乘法结果为-x^2输出-1 2。这个用例能检查你输出零多项式的逻辑。测试用例4单项式乘多项式第一个多项式3x^2第二个多项式2x^3 4x即1 3 2 2 2 3 4 1乘法结果6x^5 12x^3输出6 5 12 3。加法结果2x^3 3x^2 4x输出2 3 3 2 4 1。这个用例能检查乘法循环中对只有一个节点的多项式的处理。5.3 常见Wrong Answer原因排查我把这道题最常见的提交失败原因整理成一个表格你对照排查一下错误现象可能原因解决办法输出多了0 系数的项合并同类项后系数为0但没有删除节点在insert中判断系数为0时删除节点输出顺序是升序插入时循环条件写反检查while (curr curr-expon expon)是否保证降序多项式结果为0时没输出打印函数遇到空链表直接返回空链表要输出0 0行末多一个空格统一在项间加空格时没处理末尾用flag或者先输出第一项乘法结果少了某些项每个外层项都要乘以P2的所有项循环边界少了检查双重循环是否遍历完整加法结果漏了剩余项一个链表走完后没把另一个链表剩下的接上写两个while处理剩余链程序崩溃空指针访问检查attach、insertPoly中是否对指针判空乘法结果全是0insertPoly里系数相加后没处理或系数乘积计算错误检查coef p-coef * q-coef是否正确6. 从这道题延伸出去内存释放、性能思考与平时容易忽略的习惯6.1 动态内存到底要不要释放很多同学刷题时习惯了“不释放内存反正也没事”因为程序跑完操作系统会回收。但我要说如果你是为了学数据结构而做题而不是单纯为了AC建议养成释放内存的习惯。一个简单的释放函数可以这样写void freePoly(Polynomial P) { Polynomial tmp; while (P) { tmp P; P P-link; free(tmp); } }在main函数结尾调用三次分别释放P1、P2、product、sum。这样做的好处是以后的课程设计、大作业里如果代码被要求运行较长周期比如服务端程序内存泄漏是会被考核的。退一步讲刷题时养成的坏习惯到了面试手撕代码环节很容易暴露出来。很多面试官会故意问你“你这个链表有没有内存泄漏”如果你满脸问号那就很尴尬了。6.2 这道题的复杂度还能不能优化让我们认真看一眼乘法的时间复杂度。假设第一个多项式有n项第二个有m项那么乘积总共有nm个项产生未合并前。用“边乘边插入”的方法每一项插入有序链表最坏情况下要遍历O(nm)个节点所以最坏时间复杂度是O(nmn*m)也就是O(n²m²)。当n和m都等于20时这大约是16万次操作还好但如果n和m都到100就是1亿次那就比较吃力了。更稳妥的优化方案是“先收集、再排序、再合并”把nm个乘积项存到一个数组或临时链表里O(nm)。对结果按指数降序排序O(nm log(nm))。一次遍历合并同类项O(n*m)。这样的复杂度是O(nm log(nm))明显优于边乘边插的最坏情况。如果你要用数组存乘积项需要预先申请nm大小的数组。好在C语言里malloc一个nm大小的结构体数组很轻松。不过说实话用在这道20分题上有点“杀鸡用牛刀”了。但你理解了这条优化路径以后处理类似“多项式乘法”“卷积”问题时会更有底气。另外这道题如果指数范围小且规整完全可以用桶的思想开一个数组下标代表指数值累加系数。这个思路在处理指数范围可控、稀疏度不高的场景下是最快的O(nm指数范围)。但缺点是一旦指数范围很大比如百万级数组就浪费了。这也是“数组vs链表”这道经典选择题的意义所在——数据结构的选型取决于数据特征。6.3 再聊几句“链表”这件事本身写这道题的过程中我最大的体会是链表的操作真不是“会背就完事”而是要能自己在纸上画图。你可以试着在草稿纸上画两个多项式链表然后手动模拟一次加法、一次乘法把每个指针的走向标出来。画完你再写代码速度和准确率会明显提升。很多人觉得链表绕本质上是没建立起“节点指针”的具象画面。有一个很直观的生活类比链表就像一条铁链每个铁环里嵌着一张纸条纸条上写着“下一个环在哪里”。你手里握着一个索引指针你只能通过它找到当前的环然后顺着铁环上的标记找下一个环。你没法跳跃也没法回头。理解了这一点你就理解了单链表的一切——为什么插入要记前驱、为什么遍历只能往前走、为什么尾插要维护尾指针。如果做题时遇到“为什么我的指针不动了”这类问题不要急着看别人的代码先画图。把每次操作前后的指针指向画出来错误往往一眼就能看到。我见过太多同学卡在链表上其实不是算法不会而是“脑子里没有图”。这道题的20分本质上考察的不只是多项式的数学运算更是你能不能把抽象的线性关系用指针网络具象化。一旦你画图画顺了链表相关的题——反转链表、合并有序链表、求中间节点、判断环——都会变得轻松许多。最后说一个实用的小技巧调试链表程序时别只盯着代码看试着写一个printList函数在每次关键操作后都打印一遍当前链表内容。比如在乘法里的每个外层循环结束时打印一次结果链表你就能立刻看出是哪一项的插入合并出了问题。这种“边写边查”的调试方式比提交一次PTA等一次判错要高效得多。我自己在做链表类题目时一定会保留一个调试用的打印函数AC之后再删掉。这个习惯你可以试着用起来。 PTA一元多项式乘法与加法：链表实现详解与避坑指南
不知道有多少人和我一样第一次在PTA拼题A上刷到这道“7-2 一元多项式的乘法与加法运算”的时候心里想的是这不就是合并同类项吗初中生都会。然后自信满满地写了个数组版一提交Runtime Error或者Wrong Answer直接被20分的题教做人。这道题放在数据结构课程里考查的从来不是“你会不会算多项式”而是“你会不会用线性结构去组织数据并在组织的过程中把边界条件处理干净”。尤其是链表版本稍不留神就踩进空指针、零多项式、系数抵消的坑里。这篇东西我不打算给你抄一份标准答案就完事而是把这道题从考点拆解、数据结构选型、加法乘法实现细节、输出格式的隐藏要求到完整的可运行代码和测试用例全部过一遍。无论你是正在学《数据结构》的本科生还是在准备考研机试、找工作笔试需要巩固链表操作的读者这篇应该都能让你把这20分拿得明明白白。1. 这道20分题的考点拆解别急着写代码先看懂题目在考什么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。输出则是两行第一行是乘积结果第二行是求和结果15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0注意看输出里没有任何多余的说明文字没有“Result is”就是纯粹的一串数。很多同学第一次写的时候会把“系数 指数”写反或者多个空格少个空格这些都是扣分点。后面我会专门拿出一节来梳理输出格式的坑。1.2 数据结构选型链表还是数组这道题最经典的做法有两种数组和链表。很多学校的数据结构课程讲义里这道题的标准答案是用带头结点的单链表实现。为什么因为这道题出现在“线性表”章节之后本质上就是训练你对链表这种动态存储结构的掌握程度。用数组做当然可以做甚至代码写起来更短。核心就是开一个足够大的数组以指数为下标系数为值直接累加。但问题来了数组的大小需要预先确定万一指数很大怎么办题目如果出现x^1000这种项你得开出1001个元素如果出现x^1000000内存就有点尴尬了。数组无法体现“动态分配、按需存储”的思想而这恰恰是链表存在的意义。这题叫“数据结构与算法”课程题老师希望你练的是链表操作——创建、插入、删除、遍历、合并。你用数组做哪怕AC了课程设计的分数也未必高。所以这篇博文我会以链表为主线来讲。用链表做这道题你实际训练的是以下几项核心能力带头结点链表的创建与遍历按指数有序插入的算法两个链表合并加法时的指针移动策略两个链表逐项相乘后再合并同类项的运算组织动态内存的申请与释放。这些能力在后面的“多项式运算”“稀疏矩阵”“一元多项式求导”等题目里都会反复用到。把这道题吃透等于把链表的核心操作过了一遍。1.3 为什么带头结点的单链表写起来最顺手很多教材在讲链表时会区分“带头结点”和“不带头结点”两种写法。这道题我强烈建议你用带头结点的方式。原因很简单头结点不存数据它的作用是把“插入第一个节点”和“插入后面的节点”统一成同一种操作。比如要在链表尾部追加一个节点带头结点时无论链表当前是否为空逻辑都是“从头结点开始找到最后一个节点然后接上新节点”。不带头结点时你每次都得判断“链表是不是空的”如果不是才走找尾结点的逻辑多一层分支代码容易乱。创建带头结点的空链表初始化的写法是typedef struct PolyNode *Polynomial; struct PolyNode { int coef; // 系数 int expon; // 指数 Polynomial link; // 指向下一项 }; Polynomial createEmptyPoly() { Polynomial P (Polynomial)malloc(sizeof(struct PolyNode)); P-link NULL; return P; }头结点本身的coef和expon可以随便初始化不影响后面的运算逻辑。你只需要记住这个节点是“哨兵”从它后面的第一个节点开始才是真正的多项式项。2. 多项式加法两个指针并行扫描指数大的先走2.1 加法的核心逻辑加法是这道题里相对简单的部分但简单不等于可以掉以轻心。两个多项式相加的规则是指数相同的项系数相加指数不同的项直接照抄。用链表实现时通常的做法是用两个指针分别指向两个多项式的第一个有效节点然后比较它们当前指数的大小如果第一项的指数大于第二项的指数说明第一项在结果里应该排在前面把第一项复制到结果链表指针A后移如果第一项的指数小于第二项的指数说明第二项应该排在前面把第二项复制到结果链表指针B后移如果两项指数相等则把系数相加。如果相加后的系数不为0就生成一个新节点挂到结果链表如果系数为0这一项就消失了两个指针都后移。这个思路本质上就是“归并排序”的归并阶段那种双指针扫描。理解这一点后面学归并、合并有序链表时都会觉得顺。对应代码实现Polynomial polyAdd(Polynomial P1, Polynomial P2) { Polynomial front, rear, temp; rear (Polynomial)malloc(sizeof(struct PolyNode)); front rear; // 用front记住结果链表的头结点位置 P1 P1-link; P2 P2-link; while (P1 P2) { if (P1-expon P2-expon) { attach(P1-coef, P1-expon, rear); P1 P1-link; } else if (P1-expon P2-expon) { attach(P2-coef, P2-expon, rear); P2 P2-link; } else { int sum P1-coef P2-coef; if (sum ! 0) { attach(sum, P1-expon, rear); } P1 P1-link; P2 P2-link; } } // 剩余项直接接到结果后面 while (P1) { attach(P1-coef, P1-expon, rear); P1 P1-link; } while (P2) { attach(P2-coef, P2-expon, rear); P2 P2-link; } rear-link NULL; temp front; front front-link; // 跳过头结点 free(temp); // 释放头结点 return front; }这里有一个很关键的设计attach函数。它的作用是在链表末尾插入一个新节点。由于我们每次都要更新链表的尾指针rear所以attach接收的是rear的指针的指针。这是C语言里常见的一个细节——你需要修改调用者那边保存的尾指针值而C语言函数传值所以必须传二级指针才能让rear在函数内被更新后调用者能看到变化。2.2 attach尾插法的写法与细节attach函数的实现void attach(int coef, int expon, Polynomial *pRear) { Polynomial P (Polynomial)malloc(sizeof(struct PolyNode)); P-coef coef; P-expon expon; P-link NULL; (*pRear)-link P; *pRear P; }注意*pRear在进入函数时指向当前链表的最后一个节点。我们让它的link指向新节点然后更新*pRear为新的节点。这样调用结束后外界的rear就自动指向新链表的尾巴了。如果不传二级指针而是传Polynomial rear那么函数内部修改rear的值不会影响外面。这是一个经典C语言陷阱。很多同学链表写不好一半的bug出在“为什么我的尾指针没有移动”这种问题上。这里一定要想明白你修改的是指针变量的值还是指针指向的内存内容(*pRear)-link P修改的是“尾节点指向的下一个节点”这是内存内容不传二级指针也能改但是*pRear P修改的是“尾指针变量本身的值”这就必须二级指针才行。2.3 加法里容易忽略的边界情况加法部分有几个边界情况值得单独拎出来说。第一个情况是系数抵消。假设P1里有3 4P2里有-3 4两者指数相同系数相加等于0这一项不能在结果里出现。如果你把系数为0的节点也插入结果链表你的输出格式就错了——会输出0 4这一项这在逻辑上是错的因为0x^4等于0不是多项式的一项。第二个情况是空多项式。题目输入里给出的项数可能包含0吗实际上PTA原题的正则约束里输入的都是项数至少为1的情况。但你自己测试时应该考虑如果其中一个多项式只有一项、甚至都只有一项的情况。链表实现里只要有一个多项式为空也就是head-link为NULL加法就会全部落到“剩余项直接接上”的逻辑里。第三个情况是两个多项式完全一样加完之后系数变成原来的两倍。这个看起来没问题但要注意如果你在加法过程中修改了原链表节点的值比如直接P1-coef P2-coef而不新建节点就会破坏原数据。虽然这道题只要求输出不改原数据也能过但养成“运算不修改输入数据”的习惯是好的因为后面的复杂题目往往会要求你保留原多项式供多次使用。3. 多项式乘法先构造再合并别边乘边插3.1 两层循环逐项相乘多项式乘法的规则是第一个多项式的每一项分别乘以第二个多项式的每一项把得到的乘积项收集起来再把指数相同的项合并。用链表实现时最直接的方式就是两层循环外层遍历P1的每一项内层遍历P2的每一项让coef P1-coef * P2-coefexpon P1-expon P2-expon把结果用一个临时结果链表收集。这个过程可以用一个间接的思路理解乘法展开就是在做“每一项都乘一遍”和手算多项式时一个一个相乘再合并的过程一模一样。比如(3x^4 - 5x^2 6x - 2)乘以(5x^20 - 7x^4 3x)你先用3x^4去乘第二个多项式得到15x^24 - 21x^8 9x^5再用-5x^2去乘得到-25x^22 35x^6 - 15x^3依次类推。所有项产生之后把指数相同的项系数加起来。一种比较清晰的实现是先用P1的第一项乘以P2的所有项构造出一个“种子结果链表”然后继续用P1的第二项、第三项……去乘P2每乘出一项就插入结果链表的合适位置如果指数相同则合并系数。这种写法的好处是结果链表始终是“有序且无同类项”的最后不需要再做一次独立的合并操作。另一种实现方式是把所有乘积项放进一个临时链表不管重不重复结束后统一排序、合并同类项。这种方式代码简单但要多一次排序和遍历合并。考虑到这题数据量小怎么都无所谓但从算法素养的角度第一种“边乘边插入有序链表”的写法更优雅也更贴合“在有序链表中插入节点”这个考点。3.2 在有序链表中插入与合并我采用的方案是先构造空结果链表P然后对P1的每一项遍历P2的每一项把乘积结果通过一个专门的insertPoly函数插入到结果链表P中。insertPoly的内部逻辑是从结果链表头开始找到第一个指数小于等于当前项指数的位置如果当前位置的指数等于当前项的指数就把系数相加如果相加后系数为0删除该节点如果当前位置的指数小于当前项的指数就把新节点插到它前面。需要特别注意的是这个“寻找插入位置”的过程必须维护一个前驱指针prev。因为单链表只能往后走你要在某个节点之前插入就必须记录它的前一个节点。插入的核心操作是newNode-link prev-link; prev-link newNode。但这里有一个比插入更隐蔽的问题合并同类项后系数如果变成0需要删除节点。删除节点同样需要前驱指针。而且删除之后你不能继续用原来的当前节点指针继续走得回到前驱节点继续判断。我见过很多人在这一步翻车写出来的代码在“结果多项式有抵消项”时出错。等下在“完整代码实现”部分我会给出对应代码。3.3 乘法的时间复杂度和优化讨论直接用两层循环有序插入时间复杂度最坏是O(nmLen)其中n、m分别是两个多项式的项数Len是结果链表的长度。在题目20分题的数据范围内这个复杂度完全够用。n和m一般不超过几十Len最多是n*m所以最坏情况下也就是几十乘几十CPU毫无压力。但如果你想显摆一下自己的算法功底可以提一下更优的思路先用O(nm)算出所有乘积项并放在一个数组中或临时链表里然后排序O(nm log(nm))再按顺序合并同类项。当n、m比较大的时候这种“先收集再排序”的方式比“边乘边插入”要更稳定。因为边乘边插入需要一次次地从链表头部往下找插入位置最坏情况是O(k)的查找而k是结果链表长度整体就会退化到O(nm*k)。我自己的建议是在考场或机试环境下代码写对比代码写快更重要。选你最有把握、最容易调通的思路。如果你对链表的插入删除已经炉火纯青那就用边乘边插如果你觉得把握不大就先把乘积项全部挂到临时链表最后调用一个“排序合并”函数统一处理。考试是为了拿分不是为了耍帅。4. 输出格式这道题一半的坑都在输出上4.1 输出要求里藏着哪些细节再回头看看题目要求的输出形式。以加法的结果为例输出是5 20 -4 4 -5 2 9 1 -2 0这里每个“系数 指数”对之间用空格隔开但行末不能有额外空格。很多同学在写循环输出时习惯在每项后面打一个空格然后最后一项多了个空格这在PTA上就是Presentation Error或者Wrong Answer。处理方式有两种方式一判断当前节点是不是第一个节点不是的话先输出一个空格再输出系数指数。void printPoly(Polynomial P) { int flag 0; if (!P) { printf(0 0\n); return; } while (P) { if (!flag) { printf(%d %d, P-coef, P-expon); flag 1; } else { printf( %d %d, P-coef, P-expon); } P P-link; } printf(\n); }方式二先输出第一个节点之后每个节点前面都补一个空格。效果一样。我个人习惯用方式一因为逻辑上更统一不用单独拉出第一个节点。4.2 零多项式的输出是个大坑如果两个多项式相乘或相加的结果是零多项式怎么输出这个很多人不知道。题目明确要求如果结果是零多项式输出0 0。这里的“零多项式”是指所有项的系数都是0或者说结果里没有任何有效项。比如x (-x)结果是0。你不能什么都不输出必须输出一行0 0。在数学上“0 0”不是一个严格意义的多项式项但这就是本题的约定——用“系数0、指数0”来表示零多项式。原因很简单输出格式必须保持两行都有内容否则没法解析。所以你的打印函数必须判断链表是否为空。如果结果链表是空链表直接输出0 0\n。这里还要注意一个逻辑联动当你做合并同类项时如果某个节点的系数相加后为0你要把该节点从链表中删除。如果删除后链表变空了就说明结果多项式是零多项式。有些人的代码在系数抵消时只把系数置0而保留节点最后打印的时候虽然会输出0 指数这不符合题目要求的0 0格式。所以正确处理是系数为0就删节点而不是留下一个系数为0的脏节点。4.3 关于指数为0和系数为1/负数的输出多项式里如果有一项的指数是0意味着这是常数项。输出时不需要特殊处理就正常输出“系数 0”。比如5x^0输出为5 0。这个在题目的样例里出现过-2 0就是常数项-2。系数为1的时候正常人手写多项式会写作x^3而不是1x^3系数为-1时写作-x^3。但这道题并不要求你按照数学规范化简输出直接输出1 3也是对的。我见过有些同学在这个地方画蛇添足试图判断系数为1就不输出系数结果数据格式反而错了。切记PTA程序题是按格式判分的你和裁判之间唯一的交流就是那几行数字千万别用自己的“数学直觉”去猜输出格式一切以题目描述为准。系数为负值时直接打印负数即可比如-5 2表示-5x^2。题目没有要求你处理符号直接printf(%d, coef)就完事。4.4 指数降序排列的保证输出要求按指数降序排列。如果你的结果链表始终是有序的——比如用“边乘边插入有序链表”的方式那打印时自然就是降序。如果你用了“临时链表收集最后合并”的方式那么合并前必须先排序。这里强烈建议不要把排序和合并分成两个函数而是先用某种方法让链表有序然后单遍扫描合并同类项。一种实现思路是先把临时链表用冒泡或插入排序整理成降序再一次遍历把相邻的同类项合并。因为排好序之后指数相同的项必然是相邻的一次遍历就能合并完。如果你在排序之前合并那还得用双重循环逐个找相同的项白白增加复杂度。5. 完整代码与测试按这个模板写稳过5.1 完整可运行的C语言实现下面这份代码是我实际调试通过的版本用带头结点单链表实现乘法采用“边乘边插入有序链表”的方式。里面包含了完整的创建、插入、相加、相乘、打印、释放内存函数。我加了比较详细的注释你把它完整复制到本地用gcc编译运行再对照题目样例应当能直接通过。#include stdio.h #include stdlib.h typedef struct PolyNode *Polynomial; struct PolyNode { int coef; int expon; Polynomial link; }; // 在链表末尾接一个新节点pRear为尾指针的指针 void attach(int coef, int expon, Polynomial *pRear) { Polynomial P (Polynomial)malloc(sizeof(struct PolyNode)); P-coef coef; P-expon expon; P-link NULL; (*pRear)-link P; *pRear P; } // 读取多项式 Polynomial readPoly() { int n, coef, expon; scanf(%d, n); Polynomial front (Polynomial)malloc(sizeof(struct PolyNode)); Polynomial rear front; front-link NULL; for (int i 0; i n; i) { scanf(%d %d, coef, expon); attach(coef, expon, rear); } return front; } // 在有序链表P中插入一项保持指数降序。若指数相同则合并系数。 void insertPoly(Polynomial P, int coef, int expon) { Polynomial prev P; // 前驱指针初始指向头结点 Polynomial curr P-link; // 当前节点 // 找到插入位置curr为空或curr的指数小于等于待插入指数 while (curr curr-expon expon) { prev curr; curr curr-link; } if (curr curr-expon expon) { // 指数相同合并系数 curr-coef coef; if (curr-coef 0) { // 系数抵消删除当前节点 prev-link curr-link; free(curr); } } else { // 指数不同插入新节点到prev之后 Polynomial newNode (Polynomial)malloc(sizeof(struct PolyNode)); newNode-coef coef; newNode-expon expon; newNode-link curr; prev-link newNode; } } // 多项式加法 Polynomial polyAdd(Polynomial P1, Polynomial P2) { P1 P1-link; P2 P2-link; Polynomial front (Polynomial)malloc(sizeof(struct PolyNode)); Polynomial rear front; front-link NULL; while (P1 P2) { if (P1-expon P2-expon) { attach(P1-coef, P1-expon, rear); P1 P1-link; } else if (P1-expon P2-expon) { attach(P2-coef, P2-expon, rear); P2 P2-link; } else { int sum P1-coef P2-coef; if (sum ! 0) { attach(sum, P1-expon, rear); } P1 P1-link; P2 P2-link; } } while (P1) { attach(P1-coef, P1-expon, rear); P1 P1-link; } while (P2) { attach(P2-coef, P2-expon, rear); P2 P2-link; } rear-link NULL; return front; } // 多项式乘法 Polynomial polyMult(Polynomial P1, Polynomial P2) { P1 P1-link; P2 P2-link; Polynomial front (Polynomial)malloc(sizeof(struct PolyNode)); front-link NULL; if (!P1 || !P2) { return front; // 有零多项式时结果为空链表 } for (Polynomial p P1; p; p p-link) { for (Polynomial q P2; q; q q-link) { int coef p-coef * q-coef; int expon p-expon q-expon; insertPoly(front, coef, expon); } } return front; } // 打印多项式 void printPoly(Polynomial P) { P P-link; if (!P) { printf(0 0\n); return; } int flag 0; while (P) { if (!flag) { printf(%d %d, P-coef, P-expon); flag 1; } else { printf( %d %d, P-coef, P-expon); } P P-link; } printf(\n); } int main() { Polynomial P1 readPoly(); Polynomial P2 readPoly(); Polynomial product polyMult(P1, P2); printPoly(product); Polynomial sum polyAdd(P1, P2); printPoly(sum); return 0; }5.2 测试用例设计写完代码之后一定要自己造几组测试数据。我列几个必测的用例每个都踩到过不同的坑。测试用例1标准样例4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1预期输出15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0测试用例2指数相同、系数抵消第一个多项式2x 1第二个多项式-2x 1也就是2 2 1 1 0 1 2 -2 1 1 1 0加法结果应该为常数2即输出2 0。乘法结果呢计算一下(2x1)(-2x1) -4x^2 2x - 2x 1 -4x^2 1输出-4 2 1 0。这个用例能检查你的insertPoly在同指数合并后系数抵消的删除逻辑。测试用例3结果为0第一个多项式x第二个多项式-x即1 1 1 1 -1 1加法结果为零多项式输出一行0 0。乘法结果为-x^2输出-1 2。这个用例能检查你输出零多项式的逻辑。测试用例4单项式乘多项式第一个多项式3x^2第二个多项式2x^3 4x即1 3 2 2 2 3 4 1乘法结果6x^5 12x^3输出6 5 12 3。加法结果2x^3 3x^2 4x输出2 3 3 2 4 1。这个用例能检查乘法循环中对只有一个节点的多项式的处理。5.3 常见Wrong Answer原因排查我把这道题最常见的提交失败原因整理成一个表格你对照排查一下错误现象可能原因解决办法输出多了0 系数的项合并同类项后系数为0但没有删除节点在insert中判断系数为0时删除节点输出顺序是升序插入时循环条件写反检查while (curr curr-expon expon)是否保证降序多项式结果为0时没输出打印函数遇到空链表直接返回空链表要输出0 0行末多一个空格统一在项间加空格时没处理末尾用flag或者先输出第一项乘法结果少了某些项每个外层项都要乘以P2的所有项循环边界少了检查双重循环是否遍历完整加法结果漏了剩余项一个链表走完后没把另一个链表剩下的接上写两个while处理剩余链程序崩溃空指针访问检查attach、insertPoly中是否对指针判空乘法结果全是0insertPoly里系数相加后没处理或系数乘积计算错误检查coef p-coef * q-coef是否正确6. 从这道题延伸出去内存释放、性能思考与平时容易忽略的习惯6.1 动态内存到底要不要释放很多同学刷题时习惯了“不释放内存反正也没事”因为程序跑完操作系统会回收。但我要说如果你是为了学数据结构而做题而不是单纯为了AC建议养成释放内存的习惯。一个简单的释放函数可以这样写void freePoly(Polynomial P) { Polynomial tmp; while (P) { tmp P; P P-link; free(tmp); } }在main函数结尾调用三次分别释放P1、P2、product、sum。这样做的好处是以后的课程设计、大作业里如果代码被要求运行较长周期比如服务端程序内存泄漏是会被考核的。退一步讲刷题时养成的坏习惯到了面试手撕代码环节很容易暴露出来。很多面试官会故意问你“你这个链表有没有内存泄漏”如果你满脸问号那就很尴尬了。6.2 这道题的复杂度还能不能优化让我们认真看一眼乘法的时间复杂度。假设第一个多项式有n项第二个有m项那么乘积总共有nm个项产生未合并前。用“边乘边插入”的方法每一项插入有序链表最坏情况下要遍历O(nm)个节点所以最坏时间复杂度是O(nmn*m)也就是O(n²m²)。当n和m都等于20时这大约是16万次操作还好但如果n和m都到100就是1亿次那就比较吃力了。更稳妥的优化方案是“先收集、再排序、再合并”把nm个乘积项存到一个数组或临时链表里O(nm)。对结果按指数降序排序O(nm log(nm))。一次遍历合并同类项O(n*m)。这样的复杂度是O(nm log(nm))明显优于边乘边插的最坏情况。如果你要用数组存乘积项需要预先申请nm大小的数组。好在C语言里malloc一个nm大小的结构体数组很轻松。不过说实话用在这道20分题上有点“杀鸡用牛刀”了。但你理解了这条优化路径以后处理类似“多项式乘法”“卷积”问题时会更有底气。另外这道题如果指数范围小且规整完全可以用桶的思想开一个数组下标代表指数值累加系数。这个思路在处理指数范围可控、稀疏度不高的场景下是最快的O(nm指数范围)。但缺点是一旦指数范围很大比如百万级数组就浪费了。这也是“数组vs链表”这道经典选择题的意义所在——数据结构的选型取决于数据特征。6.3 再聊几句“链表”这件事本身写这道题的过程中我最大的体会是链表的操作真不是“会背就完事”而是要能自己在纸上画图。你可以试着在草稿纸上画两个多项式链表然后手动模拟一次加法、一次乘法把每个指针的走向标出来。画完你再写代码速度和准确率会明显提升。很多人觉得链表绕本质上是没建立起“节点指针”的具象画面。有一个很直观的生活类比链表就像一条铁链每个铁环里嵌着一张纸条纸条上写着“下一个环在哪里”。你手里握着一个索引指针你只能通过它找到当前的环然后顺着铁环上的标记找下一个环。你没法跳跃也没法回头。理解了这一点你就理解了单链表的一切——为什么插入要记前驱、为什么遍历只能往前走、为什么尾插要维护尾指针。如果做题时遇到“为什么我的指针不动了”这类问题不要急着看别人的代码先画图。把每次操作前后的指针指向画出来错误往往一眼就能看到。我见过太多同学卡在链表上其实不是算法不会而是“脑子里没有图”。这道题的20分本质上考察的不只是多项式的数学运算更是你能不能把抽象的线性关系用指针网络具象化。一旦你画图画顺了链表相关的题——反转链表、合并有序链表、求中间节点、判断环——都会变得轻松许多。最后说一个实用的小技巧调试链表程序时别只盯着代码看试着写一个printList函数在每次关键操作后都打印一遍当前链表内容。比如在乘法里的每个外层循环结束时打印一次结果链表你就能立刻看出是哪一项的插入合并出了问题。这种“边写边查”的调试方式比提交一次PTA等一次判错要高效得多。我自己在做链表类题目时一定会保留一个调试用的打印函数AC之后再删掉。这个习惯你可以试着用起来。