【2015年数据结构真题】

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

1. 给出算法的基本设计思想。
2. 使用采用C或C++语言描述算法， 给出单链表结点的数据类型定义。
3. 根据设计思想， 采用C或C++语言描述算法，关键之处给出注释。
4. 说明你所设计算法的时间复杂度和空间算杂度。

方法一：暴力求解

定义两个指针，p指向21，q指向-15，p每走一步，q就走剩下所有元素并比较，相等就删除

时间：O(m²) 空间：O(1)

typedef struct Node
{int data;          //该节点权值struct Node *link; //下一个节点
} Node;void ans(Node *HEAD)
{Node *p = HEAD->link; //外层遍历节点pNode *q, *r; //q是r的前一个节点while (p != NULL){q = p;if (abs(r->data) == abs(p->data)) //r表示待比较节点{q->link = r->link;free(r);}else   //不相同时才修改qq = q->link;}p = p->link;
}

方法二

算法的基本思想：

算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的
数值，从而只需对链表进行一趟扫描。
因为|data|≤n,故辅助数组 temp 的大小至少为 n+1,各元素的初值均
0。依次扫描链表中的各结点，同时检查 temp[|data|]的值，如果为 0，则
保留该结点，并令++temp[|data|]；否则，将该结点从链表中删除。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>typedef struct ListNode
{int data;          //该节点权值struct Node *pNext; //下一个节点
} Node,*PNODE;//筛选链表中绝对值重复的元素
void FiltrateRep(PNODE L,int len)
{int temp[len];memset(temp,0,sizeof(int)*len);//初始化位0PNODE pre,p;pre=L;while(pre->pNext!=NULL){p=pre->pNext;if(p!=NULL){if(temp[abs(p->data)]<1){++temp[abs(p->data)];//辅助数组对应元素位置+1pre=p;}else{//如果temp[p->data]大于1,正在判断的元素，是重复的元素，需要删除pre->pNext=p->pNext;free(p);}}}
}