PAT-Deduplication on a Linked List (25)

题目来源

Deduplication on a Linked List (25)

题目描述点击链接自行查看

注意点

• 注意输出的时候除了 -1，地址要补齐到 5 位数

思路简介

静态链表的模板题 判重开个哈希集合即可

遇到的问题

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;

struct SList{
int k,next=–1;
}l1[N],l2[N];
unordered_set<int>s;

void solve(){
int start,n;
cin>>start>>n;
for(int i=1;i<=n;++i){
int curr,k,next;
cin>>curr>>k>>next;
l1[curr].next=next;
l1[curr].k=k;
}
int curr=start;
int start2=–1,curr2=–1;
s.insert(abs(l1[start].k));
while(curr!=–1&&l1[curr].next!=–1){
int nextcurr=l1[curr].next;
if(!s.count(abs(l1[nextcurr].k))){
s.insert(abs(l1[nextcurr].k));
curr=nextcurr;
continue;
}

if(start2==–1){
start2=nextcurr;
curr2=start2;
l2[curr2].next=–1;
l2[curr2].k=l1[nextcurr].k;
}
else{
l2[curr2].next=nextcurr;
curr2=nextcurr;
l2[curr2].k=l1[nextcurr].k;
l2[curr2].next=–1;
}
l1[curr].next=l1[nextcurr].next;
//curr=l1[curr].next;
}
curr=start;
while(curr!=–1){
cout<<setfill('0')<<setw(5)<<curr<<' '<<l1[curr].k<<' ';
if(l1[curr].next!=–1){
cout<<setfill('0')<<setw(5)<<l1[curr].next<<'\\n';
}
else cout<<"-1\\n";
curr=l1[curr].next;
}
curr=start2;
while(curr!=–1){
cout<<setfill('0')<<setw(5)<<curr<<' '<<l2[curr].k<<' ';
if(l2[curr].next!=–1){
cout<<setfill('0')<<setw(5)<<l2[curr].next<<'\\n';
}
else cout<<"-1\\n";
curr=l2[curr].next;
}
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
int T=1;
//cin>>T;
while(T—){
solve();
}
return 0;
}