7-10 链表去重（25 分）

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

输入格式：

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

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

地址 键值 下一个结点

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

输出格式：

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

输入样例：

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

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;

struct node{
	int key;
	int next;
};

node a1[100005];
int a2[100005],a3[100005];
bool flag[100005];

int main(){
	
	int m,n;
	cin>>m>>n;
	
	int addr,key,next;
	for(int i=0;i<n;i++){
		cin>>addr;
		cin>>a1[addr].key;
		cin>>a1[addr].next;
	}	
	
	memset(flag,true,sizeof(flag));
	
	int k1=0,k2=0;
	for(int i=m;i!=-1;i=a1[i].next){
		int q = abs(a1[i].key);
		if(flag[q]){
			flag[q] = false;
			a2[k1++] = i;
		}
		else{
			a3[k2++] = i;
		}
	}
	
	printf("%05d %d ",a2[0],a1[a2[0]].key);
	for(int i=1;i<k1;i++){
		printf("%05d\n",a2[i]);
		printf("%05d %d ",a2[i],a1[a2[i]].key);
	}
	printf("-1\n");
	
	if(k2){
		printf("%05d %d ",a3[0],a1[a3[0]].key);
		for(int i=1;i<k2;i++){
			printf("%05d\n",a3[i]);
			printf("%05d %d ",a3[i],a1[a3[i]].key);
		}
		printf("-1\n");
	}
	
	return 0;
}