L2-002 链表去重 (25分)

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

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤10​0000​​ ，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

输出格式

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

输入样例：

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. 首先用一个结构体数组存放原始的键值和下一个节点。
2. 利用数组下标遍历输入的键值，遍历过程中利用一个数组来判断键值是否在前面出现过即是否重复。若该键值在前边出现过则将下标顺序放入一个数组中，若没有出现过则将该键值所在下标顺序放入另一个数组中（以我的代码为例：若键值为15，则查看key[15]，若key[15]==1，说明键值重复，将键值15所在的结构体数组下标存入nextid1；否则存入nextid中，同时key[15]=1；）

代码展示：

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
typedef struct Node
{
	int key;
	int nextid;
}node;
int main()
{
	node no[100000];//存放原始链表 
	int n,r1=0,r2=0,id,h1;
	int key[100000]={0},nextid[100000],nextid1[100000];//key数组表示是否遇到过此key绝对值，nextid存放去重后ID，nextid1存放去掉的ID 
	cin>>h1>>n;
	for(int i=0;i<n;i++)
	{
		cin>>id;
		cin>>no[id].key>>no[id].nextid;
	}
	while(h1!=-1)//遍历链表 
	{
		if(key[abs(no[h1].key)])//如果key绝对值遇到过，将当前ID放入数组nextid1中 
		{
			nextid1[r2++]=h1;
			nextid1[r2]=-1;//使存放当前ID的下一个数组元素等于-1，为输出准备 
			h1=no[h1].nextid;//改变h1使得链表向后遍历 
		}
		else//否则将ID放入数组nextid中 
		{
			key[abs(no[h1].key)]=1;
			nextid[r1++]=h1;
			nextid[r1]=-1;
			h1=no[h1].nextid;
		}
	}
	for(int i=0;i<r1;i++)//遍历输出key值去重后的链表 
	{
		if(nextid[i+1]!=-1)
			cout<<setw(5)<<setfill('0')<<nextid[i]<<" "<<no[nextid[i]].key<<" "<<setw(5)<<setfill('0')<<nextid[i+1]<<endl ;
		else//如果nextid[i+1]==-1，则在输出它的时候不需要强制输出五位
			cout<<setw(5)<<setfill('0')<<nextid[i]<<" "<<no[nextid[i]].key<<" "<<nextid[i+1]<<endl ;
	}
	for(int i=0;i<r2;i++)//遍历输出去掉的链表 
	{
		if(nextid1[i+1]!=-1)
			cout<<setw(5)<<setfill('0')<<nextid1[i]<<" "<<no[nextid1[i]].key<<" "<<setw(5)<<setfill('0')<<nextid1[i+1]<<endl ;
		else
			cout<<setw(5)<<setfill('0')<<nextid1[i]<<" "<<no[nextid1[i]].key<<" "<<nextid1[i+1]<<endl ;
	}
 	return 0;
}

PTA测试结果：

本题代码中使用到的知识点补充：

1. 为了能够使用取一个数的绝对值的函数abs(-15)=15，必须要包含头文件cmath.
2. 输出中setw(5)和setfill('0')配合使用是强制使输出结果为五位，不够五位的用0补上。它需要包含头文件 iomanip