PAT-ADVANCED1097——Deduplication on a Linked List

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805369774129152

题目描述：

题目翻译：

1097 去除链表中的重复元素

给定带有整数键的单链表L，你需要删除具有重复的键绝对值的节点。也就是说，对于每个值K，将仅保留其键的值或绝对值等于K的第一节点。同时，所有已删除的节点必须保存在单独的链表中。例如，如果L为21→-15→-15→-7→15，则必须输出21→-15→-7，并输出删除掉的节点组成的链表-15→15。

输入格式：

每个输入文件包含一个测试用例。 对于每个测试用例，第一行包含第一个节点的地址和一个正整数N(<= 10 ^ 5)，代表节点的总数。 节点的地址是5位非负整数，NULL由-1表示。

然后是N行，每行按下述形式描述一个节点：

Address Key Next

其中Address是节点的地址，Key是结点的键值，其绝对值值不超过10 ^ 4，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

知识点：链表

思路：用一个大小为10001的数组标记遍历到当前节点链表中已经出现过的绝对值

对于保留节点和删除节点，分开依次存放进两个vector集合里，最后再统一对每个节点的next进行定向。

时间复杂度和空间复杂度均是O(N)。

C++代码：

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

struct node {
	int address;
	int key;
	int next;
	node() {};
	node(int _address, int _key, int _next) : address(_address), key(_key), next(_next) {};
};

node Node[100000];
bool remainFlag[10001];	//标记链表中已经出现过的节点绝对值 

int main() {
	fill(remainFlag, remainFlag + 10001, false);
	int first, N, address, key, next, cur;
	scanf("%d %d", &first, &N);
	for(int i = 0; i < N; i++) {
		scanf("%d %d %d", &address, &key, &next);
		Node[address] = node(address, key, next);
	}
	vector<node> remained;
	vector<node> removed;
	cur = first;
	while(cur != -1){
		if(!remainFlag[abs(Node[cur].key)]){
			remained.push_back(Node[cur]);
			remainFlag[abs(Node[cur].key)] = true;
		}else{
			removed.push_back(Node[cur]);
		}
		cur = Node[cur].next;
	}
	for(int i = 0; i < remained.size(); i++){
		if(i != remained.size() - 1){
			printf("%05d %d %05d\n", remained[i].address, remained[i].key, remained[i + 1].address);
		}else{
			printf("%05d %d -1\n", remained[i].address, remained[i].key);
		}
	}
	for(int i = 0; i < removed.size(); i++){
		if(i != removed.size() - 1){
			printf("%05d %d %05d\n", removed[i].address, removed[i].key, removed[i + 1].address);
		}else{
			printf("%05d %d -1\n", removed[i].address, removed[i].key);
		}
	}
	return 0;
}

C++解题报告：