考研笔记

板子：链表按绝对值去重（2015）

题目给了 ，值域小，直接开辅助数组标记绝对值有没有出现过。扫一遍：第一次出现就标记并保留，再出现就删掉。

代码

void absDedup(LinkList head, int n) {        // 2015：|data| <= n，绝对值重复的结点只留第一个
    int *vis = (int *)calloc(n + 1, sizeof(int));   // vis[v] = 1：绝对值 v 出现过；下标要用到 n，开 n+1
    LNode *pre = head, *p;
    while ((p = pre->next) != NULL) {        // 每次看 pre 的后继 p，要删 p 时手里正好有前驱
        int v = p->data < 0 ? -p->data : p->data;
        if (vis[v]) {                        // 出现过：删掉 p，pre 不动
            pre->next = p->next;
            free(p);
        } else {                             // 第一次出现：标记，pre 后移
            vis[v] = 1;
            pre = p;
        }
    }
    free(vis);
}

复杂度：设链表有 个结点，时间 ，空间 。

例（2015 原题）：21 → -15 → -15 → -7 → 15 变成 21 → -15 → -7。

易错点

  • 辅助数组的下标是绝对值，范围 ，所以要开 个，不是 个。
  • 删除后 pre 不动，和 删除值为 x 的结点 是同一个套路。这里用 p = pre->next 放在循环条件里，可以少写一个变量更新。
  • 题目要「时间尽可能高效」，所以拿空间换时间是对的，答题时空间要写 。

链接

反向链接