1097这道题我在刷 PAT 甲级的时候卡了整整一个晚上。不是卡在算法上——它连递归都算不上就是一个单链表按绝对值去重——而是卡在两个非常隐蔽的坑上。Wa 了两三次反复对着题面看都没发现问题最后把手算样例的结果打印出来才意识到自己一直在用一个错误的前提遍历链表。如果你正在准备 PAT 甲级或者打算用这几套题练机试手感这道题其实是个特别典型的分水岭链表题看起来人畜无害真正的分都扣在细节里。这篇我就把题目完整拆一遍重点讲我踩进去的两个坑顺便分享一套我做 PAT 链表题时的通用打法应该能帮你少走不少弯路。1. 题目拆解1097 的去重规则与输出要求1.1 输入输出格式回顾先还原一下题面。PAT 的链表题跟我们平时在数据结构课本里写的不太一样它不会真给你一个用指针串好的链表因为在线评测系统没法序列化指针。输入是若干条“节点记录”每条记录包含三个字段节点地址5 位非负整数范围一般不超过 99999节点值int 类型下一节点地址可能是有效地址也可能是 -1表示链表结束第一行给两个数head头结点地址和 N节点记录条数。然后有 N 行记录顺序是打乱的你必须自己根据 next 字段把链表重新串起来。样例格式大概长这样00100 5 99999 -7 87654 23854 -15 00000 87654 15 -1 00000 -15 99999 00100 21 23854注意看记录并不是按链表顺序给的00100 是头结点它在最后一行才出现。这就是 PAT 链表题的基本套路先建地址到记录的映射再从 head 开始串。1.2 去重逻辑保留第一次摘除后续题目的核心操作是“Deduplication on a Linked List”翻译一下就是链表去重。但这里的去重不是把重复值全部删掉而是有讲究的从头结点开始遍历链表对每个节点的值取绝对值。如果这个绝对值是第一次出现节点保留在原链如果这个绝对值之前已经出现过了就把当前节点从原链上摘下来接到另一条链的尾部。最后输出两条链第一条去重后保留的节点按原链表顺序输出第二条被摘除的重复节点也按它们在原链表中的相对顺序输出输出格式和输入完全一致每行是“当前节点地址 节点值 下一节点地址”链尾的下一节点地址输出 -1。1.3 为什么这道题容易轻视说实话我刚看到这题时觉得它是甲级里少有的“送分题”。思路很简单开一个标记数组记绝对值遍历一次分流到两个容器里再分别输出。但恰恰是这种“简单题”最容易踩坑因为你会下意识地忽略两个东西题目给的 N 到底是不是链表长度输出地址时格式到底有多严格这两个问题单独拿出来都不难但放在一起足以让一份逻辑完全正确的程序 WA 到怀疑人生。下面我就把这两个坑一个个拆开讲。2. 坑一N 是记录条数不是链表长度2.1 孤立节点是怎么冒出来的这是 PAT 链表题里最经典、也最阴险的一个坑。题面第一行输入是“头结点地址”和“节点记录条数 N”。很多第一次接触 PAT 链表题的人包括当时的我都会产生一个理所当然的假设既然题目给了 N 条记录那这 N 条记录一定都是这条链表上的节点。于是遍历的时候就直接写了for (int i 0; i N; i)把每条输入记录都处理一遍。但这个假设是错的。PAT 这类题里N 只是说明后面有多少行节点记录它不等于链表长度。为什么会出现这种情况因为测试数据里完全可以存在“孤立节点”某个节点有地址、有值、有 next但整条链表从头结点开始走任何一步都无法到达它。换句话说它只是混在输入数据里并不属于这条带头结点的链表。还有一种情况某个节点的 next 指向了一个地址但这个地址对应的节点可能因为种种原因没有出现在有效遍历路径中。无论哪种情况结论都一样——你只有从 head 出发沿着 next 字段一路走下去走到的那些节点才算链表成员。2.2 错误遍历方式的现场回放我第一次提交的代码核心遍历是这样的for (int i 0; i n; i) { // 直接把第 i 条输入记录拿去判断 int addr input[i].addr; int val abs(input[i].val); if (!seen[val]) { seen[val] true; keep.push_back(input[i]); } else { remove.push_back(input[i]); } }这份代码跑样例没问题因为样例里所有输入记录恰好都能从头结点走到。但一提交就 WA。后来我构造了一个专门暴露问题的用例00100 5 00100 1 12309 12309 2 -1 88888 8 -1 99999 9 -1 77777 7 -1头结点是 00100链表实际只有两个节点00100 和 12309。后面的 88888、99999、77777 全是孤立节点。我的错误代码会把 00100、12309、88888、99999、77777 全部纳入处理最后输出一大堆节点而正确输出应该只有00100 1 12309 12309 2 -1更麻烦的情况是如果某个孤立节点的绝对值和链上某个节点恰好相同它还会提前占用 seen 标记导致链上真正的节点被误判为“重复”被错误地丢进删除链表。这时候就不是多输出几个节点的问题了而是两条链都会错乱。2.3 正确遍历从 head 出发沿 next 走到 -1正确做法很简单把头结点作为起点用 next 数组不断往后跳直到遇到 -1。for (int cur head; cur ! -1; cur nxt[cur]) { // cur 才是真正在链表上的节点 }只有这样的遍历方式才能保证你处理到的每一个节点都确实是这条链表的成员。孤立节点根本不会被访问到自然也不会干扰去重标记。2.4 这个坑的真正本质我觉得这个坑的本质是“物理存储”和“逻辑结构”的区别。PAT 的输入记录看起来像一张表好像遍历这张表就等于遍历链表。但链表是一种逻辑结构它的顺序完全由 next 字段决定跟输入记录的物理排列顺序没有任何关系。head 是这条逻辑链的唯一入口从入口出发走不到的地方就算在输入文件里写得再完整也不是这条链的一部分。想通这一点之后我再做任何 PAT 链表题第一件事就是提醒自己先把“链上的节点”筛出来再进行后续操作。3. 坑二%05d 与空链表输出环节的两个隐藏扣分点3.1 地址补零不是可选项题目明确说了节点地址是 5 位十进制数。这意味着当地址不足 5 位时前面要补零。比如地址 32 要输出成00032地址 999 要输出成00999。我第一次输出地址用的是%d样例里碰巧地址都是 5 位所以本地怎么跑都好看一提交就报格式错误。后来把所有地址输出改成%05d问题立刻消失。这里有一个非常容易被忽略的特例-1不能被格式化成%05d否则会输出-0001。必须单独判断当下一个地址是 -1 时直接输出-1不要走格式化输出那条路。3.2 删除链表为空时到底输出什么这是第二个坑里最容易被忽略的点。题面要求输出两条链表。但你想过没有如果所有节点的绝对值都互不相同那删除链表就是空的。这时候应该怎么输出很多人的第一反应是照着输出两条链的逻辑第二条链至少输出一个-1表示空链表。但这样做是错的。按照题目的实际判定逻辑如果删除链表为空就什么都不输出连-1都不要打。也就是说当removed这个容器为空时直接跳过第二段输出。如果硬要打印一个-1评测系统会认为你多输出了一行照样判 WA。还有一种更隐蔽的边界如果 head 本身就是 -1说明整条链表为空。那么两条链表都是空此时整个输出就是空的什么也不打印。这情况在测试数据里出现概率不高但严谨起见还是要处理。3.3 一个自测用例暴露全部边界我建议你在写这道题时手动构造一个能把坑都踩出来的用例比如下面这个00100 6 00000 4 99999 00100 1 12309 68237 6 -1 33218 -4 00000 99999 5 68237 12309 2 33218先手算一遍从 head 00100 出发链表顺序是00100(1) - 12309(2) - 33218(-4) - 00000(4) - 99999(5) - 68237(6) - -1绝对值序列是 1、2、4、4、5、6。所以 00000 是唯一重复节点应该被摘除到第二条链。期望输出00100 1 12309 12309 2 33218 33218 -4 99999 99999 5 68237 68237 6 -1 00000 4 -1这个用例同时覆盖了地址不足 5 位的补零、链尾 -1、删除链表非空。如果你再把99999 5 68237这条记录删掉让 68237 变成孤立节点那删除链表就空了期望输出只剩前四条。两个用例配合起来基本能把这道题所有输出边界都测到。3.4 输出的顺序陷阱还有一个很容易被“样例误导”的点输出顺序必须严格先保留链、再删除链。题目原意是先输出去重后的链表再输出去重时被摘除的节点组成的链表。你不能因为删除链短就把它放前面更不能把两条链交错输出。这个要求本身不坑人但如果你用了两个 vector 分别收集节点最后输出时一定记得先遍历 keep再遍历 remove。4. 完整 AC 解法数组模拟链表加 vector 分流4.1 数据结构设计思路因为 PAT 链表题的地址范围是有限的常见的做法是用数组模拟“地址到节点信息”的映射key[addr]地址 addr 对应的节点值nxt[addr]地址 addr 对应的下一节点地址这两个数组的长度开到 100000 以上就够用。输入时直接对号入座不需要排序。真正的处理结果放在两个 vector 里struct Node { int addr; int val; }; vectorNode kept; // 保留链 vectorNode removed; // 删除链每个 Node 只存地址和值。为什么不存 next因为输出的时候第 i 个节点的下一节点就是第 i1 个节点根本不需要原链表里的 next 信息。这样设计可以把“链表顺序”和“下一节点指向”解耦省掉大量维护工作。4.2 核心遍历与分流代码bool seen[100005] {false}; for (int cur head; cur ! -1; cur nxt[cur]) { int val key[cur]; int absVal val 0 ? -val : val; if (!seen[absVal]) { seen[absVal] true; kept.push_back({cur, val}); } else { removed.push_back({cur, val}); } }这里有几个细节值得说一下cur的初始值是 head不是 0也不是某个“第一个输入记录”。循环条件是cur ! -1而不是i N。这正是坑一的正确解法。取绝对值我用了三目运算符因为abs()函数在 C 里虽然好用但偶尔在头文件不全的旧编译器下会出问题手写反而最稳。4.3 完整可提交代码#include cstdio #include vector using namespace std; struct Node { int addr; int val; }; const int MAXN 100000 5; int key[MAXN], nxt[MAXN]; bool seen[MAXN]; void printList(const vectorNode v) { for (int i 0; i (int)v.size(); i) { printf(%05d %d , v[i].addr, v[i].val); if (i ! (int)v.size() - 1) { printf(%05d\n, v[i 1].addr); } else { printf(-1\n); } } } int main() { int head, n; scanf(%d%d, head, n); for (int i 0; i n; i) { int addr, val, nextAddr; scanf(%d%d%d, addr, val, nextAddr); key[addr] val; nxt[addr] nextAddr; } if (head -1) { return 0; } vectorNode kept, removed; for (int cur head; cur ! -1; cur nxt[cur]) { int val key[cur]; int absVal val 0 ? -val : val; if (!seen[absVal]) { seen[absVal] true; kept.push_back({cur, val}); } else { removed.push_back({cur, val}); } } printList(kept); printList(removed); return 0; }把打印逻辑封装成printList的好处是两道链表输出共用一份格式代码不会出现保留链格式对、删除链格式错的问题。4.4 为什么不建议在数组上直接改 next我见过不少人的实现思路是遍历时真的把节点从原链上摘除也就是修改nxt数组把上一个节点的 next 指向待删除节点的 next同时维护两条新链的头尾。这样做在逻辑上完全可行但代码复杂度会明显上升。你需要额外维护保留链的头结点和尾结点删除链的头结点和尾结点遍历时记录前驱节点删除第一个节点时的特殊处理一旦某个环节没维护好很容易出现“链断了”或者“两个链表串在一起”的情况。而且这道题最后输出时每条链的下一节点地址是链内相邻节点地址不是原链表里的下一个节点地址。如果你在原数组上改 next最后还是要重新整理输出顺序等于白折腾。用 vector 收集节点的思路本质上是把“链表节点”抽象成普通对象顺序天然就是最终的输出顺序。代码更短逻辑也更不容易出错。我在做 1052、1074 这些题时也沿用这个思路效果都很好。5. 从 1097 看 PAT 链表题的五条通用保命经验5.1 同类题里的同一个坑1052、1074、10321097 不是唯一一个在 N 上做文章的题。PAT 甲级里有一批链表题坑几乎是同款。1052 Linked List Sorting给 head 和 N 条记录要求把链表按节点值排序输出。如果你直接把 N 条输入记录拿去排序孤立节点会全被排进去。正确做法是先按 head 遍历收集链上节点再对收集结果排序。1074 Reversing Linked List每 K 个节点反转一次。N 不等于链表长度必须先用 head 走一遍拿到真实链长再决定最后不足 K 个的部分怎么处理。1032 Sharing找两条链的第一个公共后缀节点。如果不去分别从两个 head 遍历而是把所有输入节点拿来判断公共节点的判定会完全错乱。这几道题放在一起看你会发现它们都在反复考察同一件事能不能把“逻辑链表”和“输入记录表”区分开。只要这个意识建立起来PAT 链表题的难度直接掉一半。5.2 保命清单刷完 1097 之后我给自己总结了几条硬性规则之后遇到所有 PAT 链表题都无脑遵守拿到 head 和 N第一件事是明确链上的节点只能是“从 head 出发能走到的节点”N 只是输入行数。用数组建映射key[addr]和nxt[addr]不要真去写 malloc 链表反而更容易出错。需要分组、反转、排序的题一律先把链上节点取进 vector再对 vector 操作。输出地址一律%05d遇到-1单独判断没有例外。动手写代码前先手算一遍样例输出提交前自己补几个边界用例。5.3 做题习惯上的建议最后说一个我自己的测试习惯。每次遇到这种对输出格式有严格要求的题我不会只在脑子里“感觉没问题”而是会把样例输入复制下来用笔在草稿纸上画一遍链表写出期望输出再让程序跑。1097 这道题我就是靠这个习惯救回来的。手算时发现第二个链表的地址排序和原链表顺序完全一致才意识到我最初的错误代码把孤立节点也算进去了。之后再遇到类似题目我都会先问自己一句我遍历的是输入记录还是从 head 出发的链表作为收尾分享一个小技巧把链表输出封装成printList这样的函数把格式逻辑固定下来。以后做 1052、1074、1097 这类题只要收集好 vector输出永远只调一个函数格式分一分都不丢。这道题刷完我最大的体会是PAT 的链表题考的不是指针操作而是你能不能把一个逻辑结构从一堆散乱记录里正确还原出来。把这一步想透链表题就真的变成送分题了。