Appearance
2015·41 链表按绝对值去重：从两两比较到值域标记
本文属于「从暴力解到最优解」专题。题面白送了一个条件「|data| ≤ n」，而暴力解从头到尾没碰它——这正是它慢的原因。这道题和 2018·41 用的是同一味药：值域标记数组，空间换时间。
题目
用单链表保存 m 个整数，结点的结构为 data | link，且 |data| ≤ n（n 为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：
head ─→ 21 → -15 → -15 → -7 → 15 → NULL则删除结点后的 head 为：
head ─→ 21 → -15 → -7 → NULL要求：
(1) 给出算法的基本设计思想。 (2) 使用 C 或 C++ 语言，给出单链表结点的数据类型定义。 (3) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 (4) 说明你所设计算法的时间复杂度和空间复杂度。
总分 15 分。题面写了「时间复杂度尽可能高效」——最优性分存在，判据是时间。另外注意 (2) 是独立一问：结点定义按题面写 data + link，字段名别顺手写成 next——这问和用什么算法无关，暴力解最优解通吃。
第一步：把暴力解写对
去重的最直接想法：对每个保留下来的结点，向后扫一遍，把绝对值和它相同的结点全删掉。外层 p 从首结点走到尾，内层拿 p 的绝对值向后逐个比对。
单链表删结点有个绕不开的基本功：必须借助前驱——摘掉一个结点要改的是它前一个结点的 link。所以内层用 pre 指向「待检结点的前驱」，删除时改 pre->link 并 free，不删时 pre 才前进：
c
typedef struct ListNode {
int data; // 整数值，可正可负
struct ListNode *link; // 后继指针（题面字段名 link）
} ListNode;
#include <stdlib.h>
void dedup(ListNode *head, int n) {
// 外层：p 依次指向每个保留下来的结点（首结点在 head->link）
for (ListNode *p = head->link; p != NULL; p = p->link) {
int v = p->data;
if (v < 0) v = -v; // 当前结点的绝对值
// 内层：从 p 之后扫到尾，删掉所有绝对值等于 v 的结点
ListNode *pre = p; // pre 是待检结点的前驱
while (pre->link != NULL) {
int w = pre->link->data;
if (w < 0) w = -w;
if (w == v) {
ListNode *tmp = pre->link; // 摘除并释放
pre->link = tmp->link;
free(tmp);
} else {
pre = pre->link; // 不删才前进
}
}
}
}拿题面的例子走一遍：p = 21，后面没有绝对值 21 的，不删；p 前进到 -15，向后删掉 -15 和 15；p 前进到 -7，后面已空。结果 21 → -15 → -7 ✓。三连重复 5 → -5 → 5 也对：p = 5 一轮删掉后面两个 ✓。
复杂度：外层每个保留结点都触发一轮向后全扫，最坏（全不重复）时间
注意一个细节：这份代码的参数 n 从头到尾没用上。先记下这笔账。
它值多少分
按正确性/最优性两个维度（详见总纲）：
- 正确性：去重语义对（保留第一次出现）、比较前取了绝对值、用前驱指针摘除并 free、逻辑自洽——正确性维度的主体分拿得到。(2) 问的结点定义、(4) 问照实写
时间 空间，也都是正常得分。 - 最优性：题面要求「时间复杂度尽可能高效」，标答是
单趟；朴素两两比较 达不到，最优性档拿不到。
这道 15 分的题，暴力解保住大头。但本题的最优解只比暴力解多一个数组，升级成本是全专题里最低的一档——值得练到能直接写出最优版。
暴力解的浪费在哪
用总纲的「找浪费三问」审一遍：
有没有重算已知的东西？——有。「绝对值 15 出现过吗」这个问题，第一次遇到 -15 时答案就已经知道了；可暴力解没把它记下来，后面每次都靠重新扫链来回答。同一个问题被全表扫描反复回答，每遍只带走一个 bit。
有没有放着性质不用？——有，而且是题面白送的。「|data| ≤ n」意味着绝对值的取值范围只有 0..n 这 n + 1 个数——值可以直接当数组下标用。暴力解把 data 当成任意整数处理，参数 n 一次都没用上。408 题面不写废话：给了值域约束，就是在提示你开桶。
两条浪费指向同一个对策——总纲的第二类手段，空间换时间：把「见过哪些绝对值」记在一个以值为下标的数组里，查询和标记都是
智慧化改造：值域标记数组
开一个长度 n + 1 的标记数组 seen[0..n]，从前往后扫一遍链表：取每个结点的绝对值 v，seen[v] 已置位说明出现过，摘除该结点；否则置位并保留。整条链只扫一遍。
(2) 问的结点定义和 (3) 问的算法一起给出：
c
typedef struct ListNode {
int data; // 整数值，可正可负，|data| <= n
struct ListNode *link; // 后继指针（题面字段名 link）
} ListNode;
#include <stdlib.h>
void dedup(ListNode *head, int n) {
char *seen = (char *)calloc(n + 1, sizeof(char)); // 下标 0..n，calloc 自动清 0
if (seen == NULL) return;
ListNode *pre = head; // pre 指向"已保留链"的尾结点（首轮是头结点）
while (pre->link != NULL) {
int v = pre->link->data;
if (v < 0) v = -v; // 取绝对值
if (seen[v]) {
// 已出现过：摘除 pre->link 并释放，pre 不动
ListNode *tmp = pre->link;
pre->link = tmp->link;
free(tmp);
} else {
// 首次出现：标记并把 pre 推进
seen[v] = 1;
pre = pre->link;
}
}
free(seen);
}复杂度：每个结点最多被访问一次（要么标记后跳过，要么被摘除释放），时间
从暴力解升级过来，五个细节决定这 15 分能拿多满：
- 取绝对值别丢。桶的下标是 |data|，漏了取绝对值会把 -15 和 15 当两个值都保留，去重语义直接错。
- 删除后 pre 不前进。摘掉
pre->link后，新的pre->link是被删者的后继，下一轮接着检查它。如果删完也让 pre 前进，-15 → -15 → -15这种连续重复会被漏掉——这是本题最阴的坑。 - free 的顺序：先
tmp = pre->link，再改pre->link = tmp->link，最后free(tmp)。先 free 再读tmp->link是 use-after-free。 calloc不是malloc。seen 必须初值全 0；malloc 不清零会读到内存残留值，把没出现过的绝对值误判成出现过。这个坑和 2018·41 的标记数组一模一样。- 收尾
free(seen)。辅助数组用完释放，别留内存泄漏。
两版对照跑一遍
用题面同款输入 21 → -15 → -15 → -7 → 15（n 取 21），期望结果 21 → -15 → -7。先看两两比较版——每个保留结点都触发一轮向后扫描：
再看值域标记版——单趟扫过去，每个结点只看一眼：
演示为不带头结点的 JavaScript 等价版本（首结点必为首次出现、不会被删，故先标记首结点再从它出发；JS 由垃圾回收代劳，没有 free）；考卷上请按题面用带头结点写法（上文 C 代码）。
等价方法与升级空间
- 通用哈希表（开链法或开放定址法）：思路和标记数组相同，也能做到线性时间，但空间是
。题面既然给了「|data| ≤ n」这个有限值域，直接拿值当下标的桶就是更简单、更快的哈希——本题按桶法作答更贴题意。如果哪天题面不给值域约束，哈希表才是那个正确的替身。 - 同一味药的另一道真题：2018·41 未出现的最小正整数——同样是「值域有限 → 值当下标 → 标记数组换掉重复扫描」。两道题放在一起做，「看到值域约束就想开桶」这个反射就建立起来了。
下一步
- 在 OJ 上把两版代码都提交跑一遍：ds-2015-41 链表按绝对值去重
- 回到题库看这道题的完整解析与错因：真题库 · 数据结构