传送门
参考题解
#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; }