前言
正文
参考题解
#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;
} ~~~
京公网安备 11010502036488号