说实话PAT甲级这题我一开始是有点轻敌的。1097 Deduplication on a Linked List名字听着就是个普通链表去重思路一分钟就能想清楚代码二十分钟也能写完。结果提交之后连着WA硬是把我按在地上摩擦了几次。最后回头一个个排查发现两个坑全藏在最不起眼的地方而且都是那种“看一眼觉得没问题细想才知道错了”的细节。这篇文章不打算只贴一份代码而是把这道题从题意拆解到两个大坑再到完整实现和调试心得一次讲透。1. 题目到底考什么链表去重与地址串联1.1 题面还原与关键词题目输入给的是链表的头节点地址和节点数量。每个节点包含三个信息当前地址、键值、下一节点地址。地址是一个五位的非负整数用 -1 代表空指针也就是链表结束。要求做的事情是从给定的头节点出发遍历整条链表把“键值绝对值第一次出现”的节点保留下来把“键值绝对值已经出现过”的节点从原链表中删掉。被删掉的节点不能扔掉而是要按它们在原链表中出现的先后顺序重新串成一条独立的链表。最后按原顺序输出保留链表和删除链表。这里有几个关键词很容易被忽略绝对值、第一次出现、删除节点也要构成一条新链表。很多人做题只看“去重”两个字然后就开始写数组标记写着写着才发现输出格式和要求没那么简单。1.2 为什么不是简单数组去重如果在普通数组里做去重你先遍历一遍用哈希表记录哪些值出现过再遍历一遍筛出重复项顺序天然就是数组下标顺序逻辑非常直接。但链表不一样。链表在逻辑上虽然是线性结构物理存储却是靠“当前节点地址 下一个节点地址”这种指针关系串联起来的。输入给你的节点顺序完全可能是乱序的你不能按照输入顺序去判断谁在前谁在后更不能直接对值排序因为去重之后输出的顺序必须保持原链表的相对顺序。所以这道题的核心就是先通过 head 和 next 把真正的链式顺序恢复出来再在“这条真实的链”上做去重。听起来简单但很多人的第一个坑恰恰就踩在“没有从 head 出发恢复链表顺序”上这个后面专门讲。1.3 算法复杂度与整体可行性这道题的数据范围一般到 10^5 级别地址范围是 0 到 99999。采用静态数组 单次遍历的做法的复杂度是 O(N)空间方面用一个布尔数组记录绝对值是否出现过外加两个栈或数组保存节点地址完全够用。时间复杂度上不用有任何担心真正需要担心的是逻辑边界什么时候该补零、什么时候该输出 -1、哪些节点根本不在链表上。这些边界处理对了代码就是一遍过处理不对就是反复 WA。2. 数据结构与代码骨架2.1 结构体数组模拟静态链表链表题最常见的做法是定义结构体数组用数组下标直接模拟地址。比如struct Node { int data; int next; } node[100005];输入的时候直接根据节点地址把信息存到对应的下标位置int addr, data, next; scanf(%d %d %d, addr, data, next); node[addr].data data; node[addr].next next;之所以不用动态链表是因为地址是离散的 0 到 99999而且输入时并不会按照链表顺序给出用数组按下标存储是最直观、最不容易出错的方式。等真正要遍历的时候再通过 head 和 next 把顺序串起来。这里要注意一个细节地址是五位数读取的时候用 %d 就行但输出的时候必须补零千万不能只写 %d。2.2 去重标记绝对值是关键题目要求删除“键值绝对值重复”的节点也就是说 1 和 -1 会被视为重复。所以判断重复时必须取绝对值但输出时仍然要输出节点的原始值。判断可以用布尔数组bool appeared[100005];遍历到当前节点时取abs(node[cur].data)作为标记下标。第一次出现就标记然后放进保留链表已经出现过就放进删除链表。这里有个很容易忽略的点如果题目中值的绝对值范围很大布尔数组就要开够如果不确定也可以直接用unordered_setint。但在 PAT 这种环境下静态数组永远是最稳的零哈希冲突速度也快。2.3 遍历串联保留链与删除链整体流程就是从 head 开始用一个 while 循环沿着 next 往下走int cur head; while (cur ! -1) { int value abs(node[cur].data); if (!appeared[value]) { appeared[value] true; keep.push_back(cur); } else { removed.push_back(cur); } cur node[cur].next; }这里我用的是两个vectorint分别存保留节点的地址和删除节点的地址。push_back 的顺序天然就是它们在原链表中的顺序后面输出的时候直接按下标顺序串联即可。很多人在这一步会把数组装进 vector 之后就开始输出以为万事大吉。但真正的坑就在输出这里而且一踩一个准。3. 两个坑的实战排雷3.1 第一个坑地址必须五位数输出-1 除外这个坑可以说是“专杀细心不足的人”。题目明确写了地址是五位的非负整数比如地址 12输出必须写成 00012。如果你用%d直接输出输出的就是 12格式直接错误。正确姿势是用printf(%05d, addr)这个格式表示输出整数时至少占五位不足五位左边补零。还有一个细节最后一个节点的 next 是 -1这个不能补零必须原样输出 -1。所以代码里要把“是不是最后一个节点”单拎出来判断。我当时的写法是这样的for (int i 0; i (int)keep.size(); i) { if (i (int)keep.size() - 1) { printf(%05d %d -1\n, keep[i], node[keep[i]].data); } else { printf(%05d %d %05d\n, keep[i], node[keep[i]].data, keep[i 1]); } }注意输出“下一个节点的地址”时不能写成node[keep[i]].next而要写成keep[i 1]。因为原链表中 keep[i] 的 next 可能指向下面这个被删掉的节点如果直接输出原 next保留链表就不成链了。这一点非常关键也算是一个隐藏坑。如果你习惯用 C 的 cout也不是不行但要用setw(5)和setfill(0)而且 -1 特判一样不能少。我个人更推荐 printf因为它能在一个表达式里同时完成补零和正常数字的输出逻辑更集中。3.2 第二个坑输入里可能有一堆不在链表上的节点这个坑比格式化更隐蔽也是新手最容易想不明白的地方。题目输入的节点数量是 N但并不是所有输入节点都一定在 head 出发的链上。有些节点可能是“孤立节点”它们自成一体或者挂在别的支路上从头节点走永远走不到。如果直接遍历所有输入的节点或者更夸张一点直接遍历 0 到 99999 的所有数组下标把这些不在链表上的节点也拿去判断去重、甚至输出结果一定是错的。正确做法只有一个严格从 head 出发通过 next 一路走到底。凡是 while 循环中走不到的节点一律不参与去重判断也不参与输出。比如输入里有这样一条链00100 1 99999 99999 1 12309 12309 2 -1 68237 6 00100 33218 3 00000这里真正的链是 00100 - 99999 - 12309节点 68237 和 33218 都是无效节点。虽然它们出现在输入里但链表遍历到 12309 后 next 是 -1根本走不到它们。如果按输入顺序处理就会多输出两条假链表直接 WA。这种“输入节点不一定都在链表上”的设计在 PAT 的链表题里非常常见本质上是为了模拟真实内存中可能存在游离节点的情况。你做链表题时只要沿着 next 走就不会被干扰只要你按输入顺序硬扫基本必挂。3.3 隐藏的第三个坑删除链为空时别乱输出严格说这个不算出题人设的坑但也让不少人翻过车。如果整条链表所有节点的绝对值都不重复那么 removed 向量就是空的此时删除链表什么也不输出代码中循环自然跳过没有问题。但如果你写的输出逻辑是“先打印保留链再打印删除链删除链无论是否为空都走统一逻辑”就要注意空向量时不能访问removed[0]。我见过有人写输出循环前先打印removed[0]空 vector 直接越界运行时崩溃。另外删除链的末尾同样要输出 -1而且两个链都要完整。很多人在保留链上记得处理 -1到删除链上就忘了以为删除链不用管结尾结果还是格式错误。4. 完整可运行代码4.1 参考实现下面是我调通之后的一份完整参考代码注释写得很详细直接照着敲一遍然后自己用用例跑一遍比只看不练记忆深刻得多#include cstdio #include cstdlib #include vector using namespace std; struct Node { int data; int next; } node[100005]; bool appeared[100005]; vectorint keep; vectorint removed; void printList(const vectorint list) { for (int i 0; i (int)list.size(); i) { int addr list[i]; if (i (int)list.size() - 1) { printf(%05d %d -1\n, addr, node[addr].data); } else { printf(%05d %d %05d\n, addr, node[addr].data, list[i 1]); } } } int main() { int head, n; scanf(%d %d, head, n); for (int i 0; i n; i) { int addr, data, next; scanf(%d %d %d, addr, data, next); node[addr].data data; node[addr].next next; } int cur head; while (cur ! -1) { int value abs(node[cur].data); if (!appeared[value]) { appeared[value] true; keep.push_back(cur); } else { removed.push_back(cur); } cur node[cur].next; } printList(keep); printList(removed); return 0; }这个代码把输出封装成了函数保留链和删除链共用一套逻辑避免写两遍出错。判断 -1 时用i list.size() - 1处理空列表时循环直接不进入安全。4.2 用样例跑一遍用前面那个包含孤立节点的例子来验证输入00100 5 00100 1 99999 99999 1 12309 12309 2 -1 68237 6 00100 33218 3 00000从 00100 出发依次访问 00100、99999、12309。节点 00100 绝对值 1 第一次出现进 keep99999 绝对值 1 重复进 removed12309 绝对值 2 第一次出现进 keep。遍历结束。输出00100 1 12309 12309 2 -1 99999 1 -1这里没有输出 68237 和 33218因为它们根本不是链上的节点。同时注意保留链输出的是 00100 - 12309而不是 00100 - 99999因为 99999 已经进删除链了。5. 常见问题速查与调试心得5.1 常见问题速查表现象可能原因处理方法输出缺前导零比如输出 12 而不是 00012格式化用了%d改成printf(%05d, addr)输出里混入不在链表上的节点没有从 head 出发走 next而是扫描全部输入节点严格使用 while 循环按 next 遍历保留链或删除链在中间断开输出下一节点地址时用了原node[addr].next改为输出下一个有效节点地址list[i 1]删除链末尾没输出 -1输出逻辑只处理了保留链末尾两个链表都统一处理末尾 -1绝对值判断错误把 1 和 -1当成两个不同值直接对 data 做标记没有取绝对值使用abs(data)程序崩溃空 vector 访问下标 0输出前判断 size 是否为 0地址读入后丢失前导零信息用 int 存地址没问题读入用 %d输出用 %05d 补零即可5.2 做题心得静态链表题在 PAT 甲级里出现频率不低1097 算是其中很有代表性的一道。它不难但很有“试探性”专门考验你到底有没有理解链表“靠地址串联”的本质而不是看你会不会写快排或者哈希。我的经验是遇到这类题先花两分钟想清楚“真正的链是如何恢复的”和“输出格式到底是什么”再动手写代码。否则程序写得再漂亮都是给 WA 做铺垫。还有一个小技巧调试的时候把 keep 和 removed 里的地址逐个打印出来再对照原链表的 next 看一眼基本一眼就能看出是不是混入了孤立节点。我当时就是这么找到第二个坑的。最后再说点个人体会做完这道题之后我最大的改变是形成了两个习惯一是所有链表题都先找 head再从 head 一路 next 走到 -1绝不图省事扫描全部输入二是输出之前先在草稿纸上写清楚格式尤其是五位数补零和 -1 特判。这两个习惯在后面的 1025、1032、1052 这类链表题里帮了大忙。1097 的两个坑说白了就是“用数组思维做链表题”和“不把输出格式当回事”。如果你也在这题上卡住了别急着怀疑算法先把这两处检查一遍大概率就能把你从 WA 的泥潭里拉出来。