L2-1 链表去重（25 分)

￡神魔★判官ぃ 2022-02-28 12:40 173阅读 0赞

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

### 输入格式： ###

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 −1来表示。

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

其中`地址`是该结点的地址，`键值`是绝对值不超过104的整数，`下一个结点`是下个结点的地址。

### 输出格式： ###

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

### 输入样例： ###

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

**代码1：**

#include <cmath>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn=1e6+10;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    
    typedef struct Node{
    	int ad,v,next;
    }Node;
    Node L1[maxn],L[maxn],A1[maxn],A2[maxn];
    int vis[10010];
    
    int main(){
    	int head,n,a;
    	scanf("%d%d",&head,&n);
    	for(int i=0;i<n;i++){
    		scanf("%d",&a);
    		scanf("%d%d",&L1[a].v,&L1[a].next);
    		L1[a].ad=a;
    	}
    	int r=0;
    	while(head!=-1){
    		L[r++]=L1[head];
    		head=L1[head].next;
    	}
    	
    	int a1=0,a2=0;
    	for(int i=0;i<r;i++){
    		//printf("L[%d].v=%d\n",i,L[i].v);
    		if(!vis[abs(L[i].v)]){
    			vis[abs(L[i].v)]=1;
    			A1[a1++]=L[i];
    		}else{
    			A2[a2++]=L[i];
    		}
    	}
    	for(int i=0;i<a1;i++){
    		if(i==a1-1){
    			printf("%05d %d -1\n",A1[i].ad,A1[i].v);
    		}else{
    			printf("%05d %d %05d\n",A1[i].ad,A1[i].v,A1[i+1].ad);
    		}
    	}
    	
    	for(int i=0;i<a2;i++){
    		if(i==a2-1){
    			printf("%05d %d -1\n",A2[i].ad,A2[i].v);
    		}else{
    			printf("%05d %d %05d\n",A2[i].ad,A2[i].v,A2[i+1].ad);
    		}
    	}
    	return 0;
    }

**代码2：**

#include<iostream>
    #include<cstdio>
    #include<set>
    #include<cmath>
    using namespace std;
    const int maxn=1e5+10;
    struct Node{
    	int ad,next,data;
    }mes[maxn];
    int a[maxn],b[maxn],c[maxn];
    
    
    int main(){
    	int f,n,x;
    	scanf("%d%d",&f,&n);
    	for(int i=0;i<n;i++){
    		scanf("%d",&x);
    		scanf("%d%d",&mes[x].data,&mes[x].next);
    		mes[x].ad=x;
    	}
    	
    	int r=0,r1=0,r2=0;
    	while(f!=-1){
    		//printf("f=%05d\n",f);
    		a[r++]=f;
    		f=mes[f].next;
    	}
    	set<int> s;
    	for(int i=0;i<r;i++){
    		if(s.find(abs(mes[a[i]].data))==s.end()){
    			b[r1++]=a[i];
    			s.insert(abs(mes[a[i]].data));
    		}else c[r2++]=a[i];
    	}
    	
    	for(int i=0;i<r1-1;i++){
    		printf("%05d %d %05d\n",mes[b[i]].ad,mes[b[i]].data,mes[b[i+1]].ad);
    	}
    	printf("%05d %d -1\n",mes[b[r1-1]].ad,mes[b[r1-1]].data);
    	
    	if(r2>0){
    		for(int i=0;i<r2-1;i++){
    			printf("%05d %d %05d\n",mes[c[i]].ad,mes[c[i]].data,mes[c[i+1]].ad);
    		}
    		printf("%05d %d -1\n",mes[c[r2-1]].ad,mes[c[r2-1]].data);
    	}
    	
    	return 0;
    	
    }
    //00100 1 00100 -5  -1  一个节点的情况