PAT A1097 Deduplication on a Linked List (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
/* 题意： 将单链表中的绝对值重复的结点分离出去单独做一条链表（只保留第一个），最后 输出分离后的原链表，以及该被分离出去的链表 思路：依旧照着静态链表五个步骤的模板走，值得注意的是，这次order，不仅需要区分有效结点和无效结点， 还需要区分被移除的结点，故order的初始值可由一般的N，变为2*N，而无效结点则从N开始。有效结点的order范围 就是在[0,N),被移除结点的范围则是在[N,2*N)，而无效结点则是2*N, 这样再样通过一个排序函数即可将所有结点分为三部分, 从左到右依次是合法结点，被移除结点和非法结点。由于需要确定某个结点的data绝对值是否是第一次出现，故还需要 一个bool数组来标记。同时考虑到最后有效结点和被移除的结点都要输出，故可以设置cntValid和cntRemove来分别对 两条链表的结点个数进行计数 注意： 1、题目可能有无效结点 2、输出链表的时候，注意最后一个结点的next直接输出-1，不能用%05d输出 3、最好还是用scanf来读入数据，并且避免这样赋值node[addr]={addr,data,next,2*N} */

const int N=1e5+10;
bool exists[N];//exist[i]表示绝对值为i的是否出现过 
//步骤一 定义结构体数组 
struct Node{
	int addr,data,next;
	int order;//标记结点的序号，order==2*N表示是无效结点 
}node[N]; 
bool cmp(Node a,Node b){
	return a.order<b.order;
}
int main(){
	//步骤二 初始化 
	fill(exists,exists+N,false);//初始化时绝对值都未出现过 
	for(int i=0;i<N;i++)node[i].order=2*N;
	int head,n; 
	cin>>head>>n;
	int addr,data,next;
	//读入 
	for(int i=0;i<n;i++){
		cin>>addr>>data>>next;
		node[addr]={addr,data,next,2*N};//这里的2*N不能省略，不然测试点1错误 
	}
	//步骤三 枚举链表
	int p=head,cntValid=0,cntRemove=0; 
	while(p!=-1){
		if(!exists[abs(node[p].data)]){
			//首次出现
			node[p].order=cntValid++;
			exists[abs(node[p].data)]=true;
		}else{
			node[p].order=N+cntRemove;
			cntRemove++;
		}
		p=node[p].next;
	}
	//步骤四 排序筛选有效结点
	sort(node,node+N,cmp);
	//步骤五 输出 
	int cnt=cntValid+cntRemove;//总共输出的结点数
	for(int i=0;i<cnt;i++){
		if(i!=cnt-1&&i!=cntValid-1){//非最后一个结点
			printf("%05d %d %05d\n",node[i].addr,node[i].data,node[i+1].addr); 
		} else{
			printf("%05d %d -1\n",node[i].addr,node[i].data);
		}
	} 
	return 0;
} ~~~