L2-1 链表去重 (25分)
程序员文章站
2022-06-08 11:03:33
...
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
静态链表的使用 利用容器 不删的存在save中 删除的存在deleat中 是否删除的标准为绝对值键值不可以重复,那就开一个bool vis[N] = {false};
类似哈希表做一个映射作为标记。
还有就是要注意输出
一是格式 除链尾next为-1 其余都以%05d输出
二是next值 不用在原node上做更改直接输出下一位的address就行
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
const int N = 100010;
struct node
{
int address;
int value;
int next;
}link[N];
bool vis[N] = {false};
vector<int> delet,save;
int main()
{
int cont = 0;
int begin, n;
cin >> begin >> n;
for(int i = 0; i < n; i++)
{
int add,va,next;
scanf("%d %d %d",&add,&va,&next);
link[add].address = add;
link[add].value = va;
link[add].next = next;
}
int p = begin;
while(p != -1)
{
int index = abs(link[p].value);
if(vis[index] == false)
{
save.push_back(p);
p = link[p].next;
vis[index] = true;
}
else
{
delet.push_back(p);
p = link[p].next;
}
}
for(int i = 0; i < save.size(); i++)
{
int p = save[i];
if(i < save.size()- 1)
{
printf("%05d %d %05d\n",link[p].address,link[p].value,link[save[i+1]].address);
}
else printf("%05d %d -1\n",link[p].address,link[p].value);
}
for(int i = 0; i < delet.size(); i++)
{
int p = delet[i];
if(i < delet.size() - 1) printf("%05d %d %05d\n",link[p].address,link[p].value,link[delet[i+1]].address);
else printf("%05d %d -1\n",link[p].address,link[p].value);
}
return 0;
}