给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。
输入格式:
输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤105,为结点总数)。一个结点的地址是非负的 5 位整数,空地址 NULL 用 -1 来表示。
随后 N 行,每行按以下格式描述一个结点:
其中地址
是该结点的地址,键值
是绝对值不超过104的整数,下一个结点
是下个结点的地址。
输出格式:
首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。
输入样例 1:
1 2 3 4 5 6
| 00100 5 99999 -7 87654 23854 -15 00000 87654 15 -1 00000 -15 99999 00100 21 23854
|
输出样例 1:
1 2 3 4 5
| 00100 21 23854 23854 -15 99999 99999 -7 -1 00000 -15 87654 87654 15 -1
|
思路:
· 模板题 套路来源
· 相似题型:给一个链表,去重(去掉值或者绝对值相等的),先输出删除后的链表,再输出删除了的链表。
· 分析:静态链表求解。用结构体数组存储这个链表,大小为maxn = 1e5,Poly[i]表示地址为address的结点。在结构体中定义一个num变量,将num变量先初始化为2 * maxn。通过改变num变量的值最后sort排序来改变链表的顺序。
将没有删除的结点的num标记为cnt1,cnt1为当前没有删除的结点的个数;将需要删除的结点的num标记为maxn + cnt2,cnt2表示当前删除了的结点的个数,因为一开始初始化为了2 * maxn,所以我们可以通过对num排序达到:num = 0maxn为不删除结点,num = maxn2maxn为删除结点,num = 2maxn为无效结点
这样sort后就会按照需要输出的顺序将结点排序,我们只需要输出前cnt1+cnt2个结点即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include<bits/stdc++.h> using namespace std; const int maxn = 1e5; struct node{ int address,data,next,num=2*maxn; }Poly[maxn]; int vis[maxn]; bool cmp(node a,node b){ return a.num < b.num; } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int start,N,address,cnt1=0,cnt2=0; cin >> start >> N; for(int i=0;i<N;i++){ cin >> address; Poly[address].address = address; cin >> Poly[address].data>>Poly[address].next; } for(int i=start;i!=-1;i=Poly[i].next){ if(!vis[abs(Poly[i].data)]){ vis[abs(Poly[i].data)] = 1; Poly[i].num = cnt1; cnt1++; }else{ Poly[i].num = maxn+cnt2; cnt2++; } } sort(Poly,Poly+maxn,cmp); for(int i=0;i<cnt1+cnt2;i++){ if(i!=cnt1-1&&i!=cnt1+cnt2-1) cout<<setfill('0')<<setw(5)<<Poly[i].address<<" "<<Poly[i].data<<" "<<setfill('0')<<setw(5)<<Poly[i+1].address<<endl; else cout<<setfill('0')<<setw(5)<<Poly[i].address<<" "<<Poly[i].data<<" "<<-1<<endl; } return 0; }
|