我记得第一次做 PAT 甲级 1097Deduplication on a Linked List这道 25 分题时心里想的是链表去重这有什么难的把每个节点的 key 绝对值存下来遇到重复就删掉不就行了结果代码写出来一提交直接两个测试点答案错误。后来耐着性子一步步排查才发现 PAT 的链表题真正的坑从来不在“去重”这两个字上而在于你怎么理解“链”——节点之间的 next 关系以及输出时那个 5 位地址的补零。这道题很适合拿来当静态链表入门的第一个完整案例。不管你是刚开始刷 PAT 甲级还是在浙大翁恺老师的 C 语言课上第一次听说 PTA做完这道题你对链表遍历、去重、链表重接这一整套操作都会有比较清晰的认识。这篇文章我不光给能 AC 的代码还会把每一步选择和每个容易翻车的细节讲清楚。1. 这道题到底在考什么先复述题目再拆考点1.1 题目描述与手算演示给一个单链表头节点地址是 head另给 N 行节点信息每行是Address Key Next。Address 和 Next 都是五位非负整数地址唯一例外的 Next 值为 -1代表空指针。Key 是整数绝对值通常不超过 10^4。去重规则从链头开始对每个节点的 key 取绝对值。如果这个绝对值是第一次出现节点保留如果之前出现过了节点必须从原链表移除。移除的节点按原链表中的相对顺序连接成第二条链表。输出先输出重接后的剩余链表再输出被移除节点组成的新链表。每段都是若干行Address Key Next最后节点 Next 为 -1。我给一个可以直接手算的例子自拟数据用于理解规则00100 21 2385423854 -15 0000000000 4 9999999999 -7 8765487654 15 -1从 00100 出发链表顺序是00100(21) - 23854(-15) - 00000(4) - 99999(-7) - 87654(15) - -1逐项检查绝对值21、15、4、7、15。前四个都不同保留当走到 87654 时key 是 15绝对值 15 已经在 23854 处出现过了所以 87654 被移除。最终剩余链表00100(21) - 23854(-15) - 00000(4) - 99999(-7) - -1移除链表87654(15) - -1输出00100 21 23854 23854 -15 00000 00000 4 99999 99999 -7 -1 87654 15 -1注意第二段只有一行因为移除链只有一个节点它的 next 是 -1。这就是整个题目的基本形态。1.2 三个隐藏考点我不觉得这道题考的是“去重”本身把题目拆开它至少考三件事第一静态链表的建表和遍历。地址是五位数天然适合用数组存。你需要习惯“用地址当作下标跟着 next 字段走”这种思考方式而不是还想着 malloc 一个节点再用指针。这是 PAT 链表题的通用基础。第二去重的判定对象是绝对值。key 是 -15 和 key 是 15这两个节点在绝对值意义上算重复必须删掉后面的那个。很多人只考虑 key 本身相等结果漏掉正负相反的情况整道题理解就跑偏了。第三删除的节点还要重新组成一条链。它不是让你删完就完事而是要把所有被删除的节点按顺序收集起来并且把它们之间的 next 关系重新建立好。这一步是区分“会写代码”和“能 AC”的关键。理解了这三个考点再往下看数据结构和算法就顺理成章了。2. 数据结构选型为什么静态链表数组是这道题的王道2.1 从五位数地址想到数组下标PAT 链表题里所有节点地址都是 0 到 99999 之间的五位数。看到这个范围第一反应就应该是开一个 100000 大小的结构体数组用地址当下标struct Node { int key; int next; } node[100000];node[id].key 存的是地址为 id 的那个节点的键值node[id].next 存的是它指向的下一个节点地址。这样节点信息随便乱序输入我们都能用 O(1) 的时间拿到任意地址的 key 和 next。为什么不建议用传统的指针链表倒不是不能做而是机试环境下指针链表完全是给自己加负担。第一题目给出的节点地址是一个逻辑数字用指针动态建链时你没法天然地把这个数字映射到节点对象上还得额外建一个从地址到指针的映射表。第二输出时要求打印 5 位地址指针链表根本不知道自己在数组里的编号你还得自己在 Node 里塞一个 address 字段又是多余的。第三动态链表在删除、重接两条链的时候指针操作特别容易出错一不留神就出现悬空指针和死循环调试成本极高。而静态链表数组天然规避了这一切地址就是下标打印地址就是打印下标改 next 就是改 node[addr].next 这个整数异常直观。2.2 用 next 字段从 head 出发才能跳过无效节点这里有一个新手最容易忽略的点输入给了 N 个节点但 N 并不等于链表长度。题目给的 N 行节点信息里可能存在一部分节点根本不在我们关心的这条链表上。它们可能出现在输入里但从 head 出发永远走不到这些就是无效节点。如果不用数组而用“读入 N 个节点依次处理”的思路很容易把无效节点也当成链表节点输出去直接导致答案错误。而静态链表从 head 出发走一遍for (int p head; p ! -1; p node[p].next) { // 处理 p }沿着 next 走走到 -1 停这一路上经过的节点才是真正有效的链表节点。输入里的孤立节点根本不会被碰到天然被过滤掉了。这是静态链表最大的优势之一后续的很多 PAT 链表题都要靠这个规矩来保证正确性。2.3 空间与时间数组开 100000visited 数组开 100005空间加起来不到 1MB对 OJ 的内存限制来说毫无压力。主流程只有一次遍历时间复杂度是 O(N)其中 N 是输入节点数如果只看有效链表长度实际上更快。对 10^5 的数据规模这个复杂度非常理想。3. 核心算法一次遍历把链拆成保留链和删除链3.1 用标记数组记录已经出现的绝对值去重的核心数据结构是一个标记数组bool visited[100005];在遍历链表的时候每遇到一个节点先算出 key 的绝对值int v node[p].key; if (v 0) v -v;然后查 visited[v]。如果没标记过说明这个绝对值是第一次出现节点放入 keep 数组并把 visited[v] 置为 true如果已经标记过说明重复了节点放入 removed 数组。这里不采用 unordered_set 的原因很简单键的绝对值范围有限用数组是常数时间访问比哈希表更快、代码也更简单。只有在你吃不准 key 范围上限的时候才值得用 unordered_set 来避开数组大小问题。常规做法就是数组标记。3.2 vector 里存的是地址而不是 Node这一步看似细节实际上决定了后面代码的简洁程度。我定义vectorint keep; vectorint removed;里面存的是节点地址比如 23854、99999 这种。这样做的原因是后续我们需要按 vector 的顺序重新建立 next 关系而地址本身足够取到 key 和修改 next。如果把整个 Node 对象放进 vector反而浪费拷贝空间而且改 next 时还得回写数组多一层复杂度。遍历部分完整代码如下for (int p head; p ! -1; p node[p].next) { int v node[p].key; if (v 0) v -v; if (!visited[v]) { visited[v] true; keep.push_back(p); } else { removed.push_back(p); } }这段代码执行完之后keep 中按原链表顺序保存了所有保留节点的地址removed 中按原链表顺序保存了所有被删除节点的地址。注意“顺序”已经是它们在原链表中的出现顺序因为我们就是按遍历顺序 push 的。3.3 为什么不在遍历时就输出有的同学可能会想反正 keep 和 removed 的顺序已经出来了直接一边遍历一边输出不就行了确实可以但有一个问题每条链的最后一个节点的 next 必须是 -1而你在遍历过程中并不知道当前节点是不是该链的最后一个。尤其是 removed 链它的最后一个节点可能是原链表中的某个中间节点遍历到它时你无法预知后面还有没有重复节点。所以稳妥的做法是先收集完最后统一重接 next再输出。这也符合 PAT 链表题的一贯套路先在 vector 上完成逻辑操作最后再统一处理输出。4. 重新接链才是重头戏next 字段为什么必须二次赋值4.1 保留链的重接遍历结束后keep 里的节点地址还保留着原来的 next 指向。比如前面例子里的 23854 的 next 原本是 00000这个关系在原始链表里没错但如果 23854 之后有某个节点被删了那保留链中 23854 的 next 就应该指向下一个保留节点而不是原来的下一个节点。所以要对 keep 整体重新接一遍for (int i 0; i (int)keep.size(); i) { int addr keep[i]; if (i 1 (int)keep.size()) { node[addr].next keep[i 1]; } else { node[addr].next -1; } }逻辑很简单第 i 个保留节点的 next 就是第 i1 个保留节点的地址最后一个保留节点的 next 置为 -1。4.2 删除链的重接对 removed 也是同样的操作for (int i 0; i (int)removed.size(); i) { int addr removed[i]; if (i 1 (int)removed.size()) { node[addr].next removed[i 1]; } else { node[addr].next -1; } }这一步容易被忽略。很多第一次写这道题的人只给保留链重接了 next删除链直接沿用旧 next然后输出的时候发现删除链的某个节点 next 指向了一个保留节点怎么查都查不出错。举个例子假设原链表是 A - B - C - D - -1其中 A 和 C 的 key 绝对值相同C 要被删除。删除链是 C那 C 的 next 应该是 -1。但如果沿用旧 nextC 的 next 会指向 D。输出删除链时D 就莫名其妙地跟着 C 被输出了或者 C 后面串到了保留链里。这就是“链条没拆干净”的典型表现。所以在重接 next 时保留链和删除链都要处理缺一不可。注意PAT 链表题里有一个通用检查点——每条输出链的最后一个节点next 必须严格等于 -1。不符合这个规则多半就是 next 没有重接干净。5. 完整可提交的 C 代码5.1 带注释的 AC 代码下面这段代码在 PTA 甲级 1097 可以直接 AC。核心思路就是前面说的静态链表 标记数组 vector 收集 统一重接。#include cstdio #include vector using namespace std; struct Node { int key; int next; } node[100000]; bool visited[100005]; // 绝对值是否出现过 int main() { int head, n; scanf(%d%d, head, n); for (int i 0; i n; i) { int addr, key, next; scanf(%d%d%d, addr, key, next); node[addr].key key; node[addr].next next; } vectorint keep; // 保留节点地址 vectorint removed; // 被移除节点地址 for (int p head; p ! -1; p node[p].next) { int v node[p].key; if (v 0) v -v; if (!visited[v]) { visited[v] true; keep.push_back(p); } else { removed.push_back(p); } } // 重接保留链 for (int i 0; i (int)keep.size(); i) { int addr keep[i]; if (i 1 (int)keep.size()) { node[addr].next keep[i 1]; } else { node[addr].next -1; } } // 重接移除链 if (!removed.empty()) { for (int i 0; i (int)removed.size(); i) { int addr removed[i]; if (i 1 (int)removed.size()) { node[addr].next removed[i 1]; } else { node[addr].next -1; } } } // 输出保留链 for (int i 0; i (int)keep.size(); i) { int addr keep[i]; if (node[addr].next ! -1) { printf(%05d %d %05d\n, addr, node[addr].key, node[addr].next); } else { printf(%05d %d -1\n, addr, node[addr].key); } } // 输出移除链空则不输出 if (!removed.empty()) { for (int i 0; i (int)removed.size(); i) { int addr removed[i]; if (node[addr].next ! -1) { printf(%05d %d %05d\n, addr, node[addr].key, node[addr].next); } else { printf(%05d %d -1\n, addr, node[addr].key); } } } return 0; }5.2 输出格式的细节解读几个输出细节值得单独说。第一%05d。地址是五位数字如果直接用%d输出00100 会被打印成 100整整少两位OJ 必然判错。printf(%05d, addr)会自动补前导零。第二next 为 -1 时的处理。为什么不能直接写printf(%05d %d %05d\n, addr, node[addr].key, node[addr].next)因为 -1 用%05d打印出来是-0001这不是题目要求的-1。所以必须单独判断。第三removed 为空的处理。如果整条链中没有任何重复绝对值removed 是空的此时不应该输出任何内容。代码里的if (!removed.empty())就是干这个的。很多同学在这里少个判断导致多余输出。6. 我踩过的坑和你想不到的测试点6.1 有效节点数不等于 N前面说过输入给了 N 个节点但链表不一定包含全部。我第一次写这道题时犯了按输入顺序遍历的低级错误读一个节点就处理一个最后把孤立节点也输出成了一条“伪链表”测试点直接挂掉。正确理解输入只是给你一份节点信息的登记表真正的链表顺序必须靠 next 从 head 一路找出来。所以遍历循环只能是for (int p head; p ! -1; p node[p].next)不要用for (int i 0; i n; i)去数节点。判断有效节点集合靠的是链表的 next 指针而不是输入行数。6.2 绝对值和 key 的边界有的同学写成if (!visited[abs(key)])看着没什么问题但abs对于某些极端负值存在溢出风险。虽然本题 key 的绝对值不超过 10^4不会触发这个问题但养成习惯更好手动判断正负。代码里我写的是int v node[p].key; if (v 0) v -v;这比直接调用abs()更稳也少一次函数调用。6.3 removed 为空时的输出判断测试点会专门给一个所有 key 绝对值都互不相同的链表。这时没有节点被删除题目要求只输出去重后的链表。如果代码里无脑把 removed 从头输出一遍会因为多输出奇怪内容而答案错误。补充一个细节keep 会不会为空不会。链表的头节点是第一个访问的节点它的 key 绝对值一定是第一次出现必然被放入 keep。所以 keep 至少有一个元素不需要判空。这个性质很多人没意识到但知道以后能帮你理解为什么输出保留链时可以放心遍历。6.4 node 数组要不要初始化node 数组是全局变量默认所有字段都是 0。如果某个节点的 next 指向了一个在输入里根本没出现的地址那么 node[那个地址] 的 key 是 0next 是 0程序会把这个不存在的节点当成一个 key0、next0 的合法节点继续输出造成错误。虽然正规测试数据不会构造这种非法引用但养成防御习惯没有坏处。你可以在读入之前这么初始化for (int i 0; i 100000; i) { node[i].next -1; }这样万一出现非法地址循环会立刻停止而不是进入死循环或产生垃圾输出。PAT 的链表题基本都可以套用这个防御式写法。6.5 使用 N 计数的其他隐患还有一种错误写法是用 N 来控制遍历次数for (int p head, cnt 0; cnt n p ! -1; cnt, p node[p].next) { // ... }这种写法在链表没环、有效节点数少于 N 时也能跑对但它容易误导你让你觉得链表长度就是 N。一旦遇到无效节点你的 cnt 和实际链长对不上后面处理就可能出错。更严重的是如果题目数据存在环PAT 一般没有但你自己构造测试时可能遇到这种写法会死循环。所以统一用while (p ! -1)最省心。7. 从 1097 看 PAT 链表题的通吃套路7.1 静态链表题的四步法做完 1097你会发现 PAT 里绝大多数链表题都是同一个模子。我自己总结的四步法基本可以通吃第一步看到五位地址立刻开 node 数组存 key 和 next。 第二步从 head 出发沿 next 收集有效节点地址到 vector。 第三步在 vector 上做题目要求的逻辑操作比如排序、反转、去重。注意此时 vector 的顺序就是链表顺序你可以随意重排真正改动链表关系留到最后。 第四步按最终要求重接 next然后统一输出。1097 用到的正是这个流程收集 - 分流到 keep/removed - 各自重接 next - 输出。不需要对 node 数组做任何复杂操作所有逻辑都在两个 vector 上完成。7.2 同类题目触类旁通PAT 甲级里同样套路的题还有不少。比如 1052 Linked List Sorting先把链上的节点收集出来然后按 key 排序再重接 next 输出再比如 1074 Reversing Linked List把节点收集到 vector 后按 K 个一组反转然后重接 next 输出。这几道题只要你吃透了 1097 的四步法基本上看一眼题目就能写出骨架剩下的只是中间那一步“在 vector 上做什么操作”的区别。我个人的习惯是遇到链表操作题先不要急着写排序或反转的逻辑而是先把收集有效节点这件事做完。很多时候题目描述里藏着无效节点或者重复节点的坑一旦你把有效链表单独拿出来后面所有操作都变得非常干净。7.3 为什么这类题值得练有人觉得这种“用数组模拟链表”的题太应试跟工作没什么关系。我不太同意。实际工程里链表节点的内存地址确实可以被当成数组下标来管理比如操作系统的页框管理、内存池的空闲链表、数据库缓冲池里的 LRU 链表都是静态数组加指针或索引的方式。PAT 这道题让你练的“先收集、再重排、最后重建链接”的思路在这些场景下同样适用。至少从刷题的角度1097 是一道性价比很高的 25 分题它把静态链表、哈希去重、链表重接、格式化输出几个常见考点一次性串起来了。如果你能把这道题完整讲给别人听说明你已经把 PAT 链表题的基础打牢了。我个人在实际操作中的体会是这道题最容易丢分的从来不是算法而是对“链”的理解。我第一次提交错的那两个测试点不是去重逻辑错了而是删除链的 next 没重接、无效节点混进了输出。后来我每次写完链表题都会强制自己检查两遍第一遍所有输出的节点是不是真的从 head 出发能走到第二遍每条链最后一个节点的 next 是不是 -1。就靠这两个检查我后面再没在 PAT 链表题上丢过格式分。如果你正卡在这道题上不妨先别看别人的题解照这个思路自己重写一遍再把错误测试点的数据打出来感受一下静态链表和“重新接链”的含义。