思路:用一个bool型的vector来存储每一个元素的绝对值是否出现过。注意在遍历链表中的每一个元素时,只有该元素没出现过才令前指针向后指,如果重复的话前指针不动。
基本操作就是y总的两个数组e[N],ne[N],删除结点操作。
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int M=10000;
const int N=100010;
typedef pair<int,int> PII;
vector<PII> dup; //存放重复数据及其地址
int e[N],ne[N],v[M];
int main(){
for(int i=0;i<M;i++){ //初始化所有的key都没有出现过
v[i]=0;
}
int n,head;
int idx=0; //重复链表的头节点从0开始
scanf("%d%d",&head,&n);
for(int i=0;i<n;i++){
int add,key,next;
scanf("%d%d%d",&add,&key,&next);
e[add]=key;
ne[add]=next;
}
int pL=head;
// int pR=ne[ne[head]];
v[abs(e[pL])]=1;
for(int i=ne[head];i!=-1;i=ne[i]){ //从头节点的下一个结点开始比较方便
if(v[abs(e[i])]==1){ //e[i]已经出现过
ne[pL]=ne[i];
dup.push_back({i,e[i]}); //{add,key} 有重复的话就不用移动pL
}
else{
v[abs(e[i])]=1;
pL=ne[pL]; //没有重复才继续移动pL
}
}
for(int i=head;i!=-1;i=ne[i]){
if(ne[i]!=-1){
printf("%05d %d %05d\n",i,e[i],ne[i]);
}
else{
printf("%05d %d -1\n",i,e[i]);
}
}
for(int i=0;i<dup.size();i++){
if(i!=dup.size()-1)
printf("%05d %d %05d\n",dup[i].first,dup[i].second,dup[i+1].first); //因为找重复元素的ne数组比较麻烦,所以采取了dup[i+1]的方式找到下一个元素的地址
else
printf("%05d %d -1\n",dup[i].first,dup[i].second);
}
return 0;
}