题目:
分析:时间复杂度尽可能高效,提示可能存在一种空间换时间的算法
思路一:空间换时间
思考:开数组储存结点数据域,对于只出现一次或多次出现第一次的,保留,对于多次出现的,删除。
#include <iostream>
#include <cmath>
using namespace std;
typedef struct Node
{
int data;
struct Node* next;
//数据域整型,指向空
}node,*list;//单个节点,链表指针
int n;
int create(list &L)
{
node*t,*r;//临时指针和尾指针
r=L;
cin>>n;
for(int i=0;i<n;i++)
{
t=new node;
scanf("%d",&t->data);
t->next=NULL;
r->next=t;
r=t;
}
}
node* check(list &head)
{
//为了方便,固定n
int *a=new int[1001]{0};//申请数组空间
int len2=0;//为了输出数组,因为有可能把指向NULL的结点都删掉
node*p=head->next,*q=head->next;
for(;p!=NULL;p=p->next)
a[abs(p->data)]++;//哈希思想
p=head;//记得指针要重置
while(q!=NULL)
{
int num=abs(q->data);
if(a[num])
{
len2++;
p->next=q;
q=q->next;
a[num]=0;
p=p->next;
}
else
{
node*t=q;
q=q->next;
p->next=q;
delete t;
}
}
delete [] a;
/*输出,用于调试
for(head=head->next;len2;len2--)
{
cout<<head->data<<' ';
head=head->next;
}*/
return head;
}
void print(list L)
{
node*t;
t=L->next;
while(t!=NULL)
{
cout<<t->data<<' ';
t=t->next;
}
}
int main()
{
list L1;//单链表/头指针
L1=new node;//创建单链表
L1->next=NULL;
create(L1);//插入值
auto ans=check(L1);
return 0;
}