给定一个带有整数键的单链表 L，您应该删除具有重复的键绝对值的结点。也就是说，对于每个值 K，仅保留其键的值或绝对值等于 K 的第一个结点。同时，所有删除的结点必须保留在单独的列表中。例如，给定 L 为 21→-15→-15→-7→15，则必须保留下来的链表为 21→-15→-7，已删除列表为-15→15。
输入第 1 行给出第 1 个链表首个结点的地址和结点总个数正整数 N。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。接下来有 N 行，每行格式为：Address Data Next，其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
首先输出结果链接列表，然后输出已删除列表。每个结点都占一行，并以与输入中相同的格式打印。
我们依然可以用静态链表的方式存储给出的各个结点信息，以结点地址作为结点在静态链表数组中的下标。为了方便，静态链表数组的元素类型可以是array<gg,2>，负责储存数据域和下一个地址。由于所给的地址是 5 位非负整数，静态链表的长度可以定义成${10}^6$，就可以表示所有的结点。
定义unordered_set<gg>us负责存储已经出现过的链表中结点数据域的绝对值，lst1 存储链表剩余的结点地址，lst2 存储链表删除的结点地址。由所给链表开始地址处开始遍历整个链表，如果当前结点的数据域的绝对值没有在 us 中找到，向 us 中插入该结点数据域的绝对值，并向 lst1 插入该结点地址；否则向 lst2 中插入该结点地址。按要求输出 lst1 和 lst2 中的内容即可
- 题目给出的结点中可能有不在链表中的无效结点。
- 输出时结点地址除-1 外要有 5 位数字，不够则在高位补 0。所以地址-1 要进行特判输出。
- 注意如果给定的初始地址就是-1，即给定的链表是空表的情况，此时只输出一行“0 -1”。
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
vector<array<gg, 2>> input(gg(1e6), {-1, -1});
void output(vector<gg>& lst) {
if (lst.empty()) {
return;
}
for (gg i = 0; i < lst.size() - 1; ++i) {
cout << setw(5) << lst[i] << " " << input[lst[i]][0] << " " << setw(5)
<< lst[i + 1] << "\n";
}
cout << setw(5) << lst.back() << " " << input[lst.back()][0] << " -1\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
gg start, ni;
cin >> start >> ni;
if (start == -1) { //为空链表时直接结束程序
return 0;
}
for (gg i = 0; i < ni; ++i) {
gg address, data, nextA;
cin >> address >> data >> nextA;
input[address] = {data, nextA};
}
vector<gg> lst1, lst2;
unordered_set<gg> us; //存储已出现过的结点值的绝对值
while (start != -1) {
gg v = abs(input[start][0]);
if (us.count(v)) {
lst2.push_back(start);
} else {
lst1.push_back(start);
us.insert(v);
}
start = input[start][1];
}
cout << setfill('0');
output(lst1);
output(lst2);
return 0;
}