【算法题】7.删除链表中所有[绝对值]重复的元素

题目

⽤单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计⼀个时间复杂度尽可能⾼效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第⼀次出现的结点,⽽删除其余绝对值相等的结点。

题目大意：

删除链表中所有[绝对值]重复的元素，使得每个元素只出现一次。

输入：

{21,-15,15,-7,15}，n = 21

输出：

{21,-15,-7}

解析：

1. 开辟n个int类型的连续的空间指针为p，并将其置为0。
2. 遍历m个整数,取其绝对值x，若p+x的位置为0，则第p+x的位置设置为1。若已经为1，则删除结点。

复杂度解析

时间复杂度：
空间复杂度：

代码

void DeleteEqualNode(LinkList *L,int n){
 int *p = alloca(sizeof(int) *n);
 LinkList r = *L;
 for (int i = 0; i < n; i++)
 {
     *(p + i) = 0;
 }
 LinkList temp = (*L)->next;
 while (temp != NULL){
     if (p[abs(temp->data)] == 1)
     {
         r->next = temp->next;
         free(temp);
         temp = r->next;
     }else{
         p[abs(temp->data)] = 1;
     }
 }
}