[数据结构与算法]PAT——1097 Deduplication on a Linked List 甲级

题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805369774129152

题意

给出一个链表，输出去重（绝对值相同即为重复，保留顺序靠前的那个节点，其余删除）后的链表，以及包含所有被删除的节点的链表

代码解析

重点就是vis数组来判断是否重复，另外就是注意输出时的格式，整体难度不大

AC代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int key,next;
}node[100005]; 
vector<int> ans1,ans2;
int vis[100005];
int main()
{
	int root,n;
	cin>>root>>n;
	for(int i=0;i<n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		node[x].key=y;
		node[x].next=z;
	}
	int st=root;
	while(st!=-1)
	{
		if(vis[abs(node[st].key)]==0)
		{
			vis[abs(node[st].key)]=1;
			ans1.push_back(st);
		}
		else
			ans2.push_back(st);
		st=node[st].next;
	}
	for(int i=0;i<ans1.size();i++)
	{
		if(i!=ans1.size()-1) printf("%05d %d %05d\n",ans1[i],node[ans1[i]].key,ans1[i+1]);
		else printf("%05d %d -1\n",ans1[i],node[ans1[i]].key);
	}
	for(int i=0;i<ans2.size();i++)
	{
		if(i!=ans2.size()-1) printf("%05d %d %05d\n",ans2[i],node[ans2[i]].key,ans2[i+1]);
		else printf("%05d %d -1\n",ans2[i],node[ans2[i]].key);
	}
}