给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。
输入格式：
输入第一行包含链表第一个结点的地址、以及结点个数N（<= 105 的正整数）。结点地址是一个非负的5位整数，NULL指针用-1表示。
随后N行，每行按下列格式给出一个结点的信息：
Address Key Next
其中Address是结点的地址，Key是绝对值不超过104的整数，Next是下一个结点的地址。
输出格式：
首先输出去重后的链表，然后输出被删除结点组成的链表。每个结点占一行，按输入的格式输出。
输入样例:
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
题意：给你一个打乱的链表，需要重新整理链表让它按照一定的顺序，并把键值的绝对值有重复的结点删除。并把没有重复的链表，和删除的链表输出，中间的数代表键值。
例如：00100是起始值。把00100做为链表的头，按照一定的顺序排得到
00100 21 23854 23854 -15 00000 00000 -15 99999 99999 -7 87654 87654 15 -1
两条两条的看，如：00100 21 23854 23854 -15 00000第一条和第二条的键值的绝对值不一样21和-15，所以21这一条链就可以确定下来。23854 -15 00000 00000 -15 99999第二条和第三条的键值的绝对值都为15，所以中间的00000 00000 -15删除掉，变成1523854 -15 99999。以此类推。
输出
第一部分：没有重复的
00100 21 23854 23854 -15 99999 99999 -7 -1
第二部分：删除的
00000 -15 87654 87654 15 -1
思路：
1.定义一个结构体
struct node{ int key;//表示键值； Int next;//表示下一个的id }a[100100]
让结构体的a的下标为每组数据开头第一个地址例如：
a[00100].key=21 a[00100].next=23854
每次把当前的next放入a[]中就可以把这条链表建立起来；
2.写一个方法来删除
用一个标记数组flag[]来记录键值是否重复，开始把第一个地址做标记
每次把头和尾传进去例如00100 和 23854
如果a[23854].next的键值没有用过就把23854和a[23854].next传入再判断
如果a[23854].next的键值用过,就让a[00100].next=a[23854].next
这样就删除重复的了；再写一个结构体把删除的结点记录下来。
然后把新链表的头尾00100和a[23854].next传入再判断。
代码：
#include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; struct node //放没有重复的链表 { int key; int next; }a[101000]; struct del //放删除的链表 { int id; int key; }b[101000]; int flag[100100]={0}; int m=0; void delet(int pre,int next) { int k=0; if(next==-1)//链尾时 return ; if(flag[abs(a[next].key)]==0)//改链表没有重复 { flag[abs(a[next].key)]=1;//做标记 delet(next,a[next].next);//传入下一条链表的头尾 }else//重复时 { a[pre].next=a[next].next;//当前的头等于下一个的尾巴 b[m].id=next;//记录删除的地址 b[m].key=a[next].key;//记录删除的键值 m++; delet(pre,a[next].next);传入当前链表的头，和下一条的尾巴 } } void print1(int n) { while(a[n].next!=-1) { printf("%05d %d %05d\n",n,a[n].key,a[n].next); n=a[n].next; } printf("%05d %d %d\n",n,a[n].key,a[n].next); } void print2() { if(m>1) { int i; for(i=0;i<m-1;i++) { printf("%05d %d %05d\n",b[i].id,b[i].key,b[i+1].id); } printf("%05d %d -1\n",b[m-1].id,b[m-1].key); } } int main() { int n,start,tstart,key,tnext; scanf("%d%d",&start,&n); while(n--) { scanf("%d%d%d",&tstart,&key,&tnext); a[tstart].key=key; a[tstart].next=tnext; } flag[abs(a[start].key)]=1; delet(start,a[start].next); print1(start); print2(); return 0; }
