题目

用单链表保存 m 个整数，结点的结构为 data | link，且 |data| ≤ n（n 为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：

list head: 21, -15, -15, -7, 15

则删除结点后的 head 为：

list head: 21, -15, -7

要求：

(1) 给出算法的基本设计思想。

(2) 使用 C 或 C++ 语言，给出单链表结点的数据类型定义。

(3) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(4) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：开一个长度为 n+1 的辅助数组 seen[]（标记 |data| 是否已出现过），从前往后扫一遍单链表——首次见到某个绝对值时标记并保留结点，再次见到则删除该结点。

为什么用辅助数组而不是两两比较？

最朴素思路：双层循环——外层 i 固定一个结点，内层 j 删除 i 之后所有 |val| 与 i 相同的结点。但这是 O(m²)，慢。

题面给了"|data| ≤ n"的关键约束——意味着绝对值的取值范围只有 0..n（n+1 个可能值）。开一个长度 n+1 的数组 seen[]，下标对应绝对值，O(1) 查询/标记某个绝对值是否出现过，把整个去重压成 O(m) 单趟扫描。

算法流程：

1. calloc 出 seen[0..n]，全 0；
2. 从头结点开始，用 pre 指向"当前已保留链"的尾部（初始 pre = head）；
3. 循环检查 pre->next：
   • 取 v = |pre->next->data|；
   • 若 seen[v] == 1（之前出现过）→ 删除 pre->next（绕过它，并 free 掉），pre 不动；
   • 若 seen[v] == 0（首次出现）→ 标记 seen[v] = 1，pre 前进到 pre->next；
4. 直到 pre->next == NULL。

(2) 单链表结点数据类型定义

typedef struct ListNode {
    int              data;         // 整数值，可正可负
    struct ListNode *link;         // 后继指针（题面字段名 link）
} ListNode;

(3) 代码实现

#include <stdlib.h>

void dedup(ListNode *head, int n) {
    char *seen = (char *)calloc(n + 1, sizeof(char));   // 下标 0..n，标记某绝对值是否出现
    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 并释放
            ListNode *tmp = pre->link;
            pre->link = tmp->link;
            free(tmp);
        } else {
            // 首次出现：标记并把 pre 推进
            seen[v] = 1;
            pre = pre->link;
        }
    }

    free(seen);
}

关键点说明：

• 必须用"前驱指针 pre"删结点：单链表删除当前结点需要前驱（要改 pre->link）。常见错法是 cur = head->link; while(cur) 然后想删 cur——实现起来要单独维护前驱，不如直接用 pre 看下一个。
• 取绝对值时小心边界：v < 0 ? -v : v。题面 |data| ≤ n 说明 v 不会超过 n，可作 seen[v] 下标。
• 删除后 pre 不前进：删除 pre 后面那个结点后，新的 pre->link 是原本的"被删者的下一个"，下一轮接着检查这个新的 pre->link。如果误把 pre 也前进了，会漏掉相邻两个重复的情况（例如 ..., -15, -15, ..., 第二个 -15 删完后 pre 不动正好处理后续）。
• seen 用 char 而非 int：每槽 0/1，char 即可。calloc 自动清 0。

(4) 复杂度分析

• 时间复杂度 ：每个结点最多被访问一次（要么标记并跳过，要么释放后 pre 不动但下一轮检查的是新的 link）。
• 空间复杂度 ：辅助数组 seen[0..n] 占 n+1 字节。

编者注（生僻术语）：本题的 seen[] 数组本质是"值域桶式哈希表"——因为 |data| ∈ [0, n] 是有限整数，可以直接拿值当下标。如果题面没有"|data| ≤ n"这条约束（值域无限大），就要用真正的哈希表（开链法或开放定址法），空间复杂度变 O(m)。考研在限定值域时，桶法永远比哈希更快、更简单。