数据结构
2015-41
用单链表保存 m 个整数，结点的结构为[data][link]，且 |data| ≤ n（n 为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 HEAD 如下：
则删除结点后的 HEAD 为
要求：
- 给出算法的基本设计思想。
- 使用 C 或 C++ 语言，给出单链表结点的数据类型定义。
- 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
- 说明你所设计算法的时间复杂度和空间复杂度。
答案
（1）算法的基本设计思想：
使用一个辅助数组记录链表中已出现的绝对值，数组大小为 n+1，初始化为 0。遍历链表，对于每个结点的绝对值，若对应数组元素为 0，则保留结点并将数组元素置 1；否则删除该结点。这样只需一趟扫描，用空间换时间。
（2）单链表结点的数据类型定义：
typedef struct node {
int data;
struct node *link;
} NODE;
typedef NODE *PNODE;（3）算法描述（C语言）：
void func(PNODE h, int n) {
PNODE p = h, r;
int *q, m;
q = (int *)malloc(sizeof(int) * (n + 1)); // 申请 n+1 个位置的辅助空间
for (int i = 0; i < n + 1; i++) // 数组元素初值置 0
*(q + i) = 0;
while (p->link != NULL) {
m = p->link->data > 0 ? p->link->data : -p->link->data; // 判断该结点的 data 是否已出现过
if (*(q + m) == 0) {
*(q + m) = 1; // 首次出现
p = p->link; // 保留
} else {
r = p->link; // 重复出现
p->link = r->link; // 删除
free(r);
}
}
free(q);
}（4）时间复杂度和空间复杂度：
时间复杂度为 O(m)，其中 m 为链表结点数；空间复杂度为 O(n)，其中 n 为给定的绝对值上限值。