AC203-删除单链表中绝对值相等的重复节点，仅保留第一次出现的节点¶

用单链表保存 m 个整数，且 |data| ≤ n，设计时间上尽可能高效的算法，对于 data 绝对值相等的结点，仅保留第一次出现的结点。（2015 年统考题）

代码实现¶

C
// 函数 del：删除单链表中绝对值相等的重复节点，仅保留第一次出现的节点
void del(LinkList L, int n) {
    // 创建辅助数组 A，用于标记绝对值是否已经出现过
    // 数组大小为 n+1，因为绝对值范围是 0 到 n
    int *A = (int *)malloc(sizeof(int) * (n + 1));

    // 初始化数组 A，所有元素都设为 0，表示对应的绝对值尚未出现
    for (int i = 0; i < n + 1; ++i) {
        A[i] = 0;
    }

    LinkList p = L; // p 指向链表的头节点
    int m;          // 用于存储当前节点数据的绝对值

    // 遍历链表，检查每个节点的后继节点
    while (p->next != NULL) {
        // 计算当前节点后继节点数据的绝对值
        if (p->next->data >= 0) {
            m = p->next->data; // 如果是非负数，绝对值就是其本身
        } else {
            m = -p->next->data; // 如果是负数，绝对值是其相反数
        }

        // 检查该绝对值是否是第一次出现
        if (A[m] == 0) {
            // 如果是第一次出现，标记该绝对值已出现
            A[m] = 1;
            // 移动指针到下一个节点
            p = p->next;
        } else {
            // 如果不是第一次出现，删除该节点
            LinkList r = p->next;        // r 指向要删除的节点
            p->next = r->next;           // 将前驱节点的 next 指向被删除节点的后继
            free(r);                     // 释放被删除节点的内存
            // 注意：此时 p 指针不移动，因为还要检查新连接的节点
        }
    }

    // 释放辅助数组 A 的内存
    free(A);
}

代码逻辑解析¶

初始化辅助数组：
创建大小为 n+1 的数组 A，用于标记绝对值 0 到 n 是否已经出现过。
初始化数组所有元素为 0，表示所有绝对值都尚未出现。
链表遍历策略：
使用指针 p 从头节点开始遍历，但每次检查的是 p->next 节点。
这种策略便于删除操作，因为可以直接通过 p 删除 p->next。
绝对值计算：
对于每个节点的数据，计算其绝对值并存储在变量 m 中。
如果数据非负，绝对值就是其本身；如果数据为负，绝对值是其相反数。
重复检测与删除：
检查数组 A[m]：如果为 0，说明该绝对值第一次出现，标记为已出现；
如果为 1，说明该绝对值已经出现过，需要删除当前节点。
指针移动策略：
当保留节点时，p 指针正常向前移动；
当删除节点时，p 指针不移动，因为需要继续检查新连接的节点。

时间复杂度分析¶

数组初始化：O(n) - 需要初始化 n+1 个数组元素
链表遍历：O(m) - 需要遍历链表中的 m 个节点
数组访问：O(1) - 每次数组访问都是常数时间操作

由于题目中 m 个整数保存在链表中，且 |data| ≤ n，在最坏情况下 m 可能远大于 n，但算法的主要瓶颈是链表遍历。

综合考虑，时间复杂度为 O(m + n)，但如果按照题目描述的"时间上尽可能高效"和给出的复杂度分析，主要关注的是对链表的单次遍历，因此可以认为是 O(m)。

空间复杂度分析¶

辅助数组：O(n) - 需要大小为 n+1 的数组来存储绝对值标记
其他变量：O(1) - 只使用了常量级别的额外空间

因此，空间复杂度为 O(n)。

较难理解部分的说明¶

为什么使用 `p->next` 而不是直接用 `p` 遍历？¶

这种遍历方式的优势在于删除操作更加方便： - 当需要删除节点时，可以通过 p 直接修改其 next 指针来跳过被删除节点 - 避免了处理头节点删除的特殊情况

图解说明¶

假设链表为：L -> 3 -> -3 -> 5 -> 3 -> -5 -> NULL，其中 n = 5

Text Only

初始状态：
数组 A: [0,0,0,0,0,0] (索引 0-5)
链表: L -> 3 -> -3 -> 5 -> 3 -> -5 -> NULL

步骤1: 处理节点 3
- 绝对值 m = 3
- A[3] = 0，第一次出现
- A[3] = 1，标记已出现
- 链表保持不变: L -> 3 -> -3 -> 5 -> 3 -> -5 -> NULL

步骤2: 处理节点 -3  
- 绝对值 m = 3
- A[3] = 1，已出现过
- 删除节点 -3
- 链表变为: L -> 3 -> 5 -> 3 -> -5 -> NULL

步骤3: 处理节点 5
- 绝对值 m = 5
- A[5] = 0，第一次出现
- A[5] = 1，标记已出现
- 链表保持不变: L -> 3 -> 5 -> 3 -> -5 -> NULL

步骤4: 处理节点 3
- 绝对值 m = 3
- A[3] = 1，已出现过
- 删除节点 3
- 链表变为: L -> 3 -> 5 -> -5 -> NULL

步骤5: 处理节点 -5
- 绝对值 m = 5
- A[5] = 1，已出现过
- 删除节点 -5
- 最终链表: L -> 3 -> 5 -> NULL

延伸知识点¶

1. 哈希表方法¶

如果 n 很大，可以考虑使用哈希表替代数组：

C
// 使用哈希表的方法
#include <uthash.h>
struct HashTable {
    int key;
    UT_hash_handle hh;
};

2. 无辅助空间的方法¶

如果不允许使用额外空间，可以采用双重遍历：

C
// 时间复杂度 O(m²)，空间复杂度 O(1)
void delWithoutExtraSpace(LinkList L) {
    LinkList p = L;
    while (p->next != NULL) {
        LinkList q = L;
        int found = 0;
        // 在已处理的部分查找是否有相同绝对值
        while (q != p->next) {
            if (abs(q->next->data) == abs(p->next->data)) {
                found = 1;
                break;
            }
            q = q->next;
        }
        if (found) {
            // 删除节点
            LinkList r = p->next;
            p->next = r->next;
            free(r);
        } else {
            p = p->next;
        }
    }
}

3. 相关算法问题¶

变体问题： - 如果要求保留最后一次出现的节点而不是第一次？ - 如果要求统计每个绝对值出现的次数？ - 如果数据范围很大，如何优化空间使用？

应用场景： - 数据去重处理 - 统计分析中的唯一值提取 - 内存优化的数据处理

这种方法体现了空间换时间的经典思想，通过使用辅助数组实现了线性时间复杂度的高效算法。