Description:

给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。

Input:

输入第一行包含链表第一个结点的地址、以及结点个数N（<= 105 的正整数）。结点地址是一个非负的5位整数，NULL指针用-1表示。

随后N行，每行按下列格式给出一个结点的信息：

Address Key Next

其中Address是结点的地址，Key是绝对值不超过104的整数，Next是下一个结点的地址。

Output:

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

Sample Input:

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

Sample Output:

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

题目链接

这道题目可以用一个二维数组记录地址、数字的对应关系和下一个地址，然后通过头节点地址依次循环往下遍历链表，用一个set容器存储遍历过的数字的“绝对值”，然后在遍历的时候通过set.count()判断set容器中是否存在这个值，若存在则将它和它的地址加到另一个vector容器中储存，若不存在则直接按照题目要求输出相应的地址和数字并将数字加入set容器中，最后再依次输出vector容器中的相应的数字和地址。
注意头节点去重（绝对值！）！

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double e = 2.718281828459;

struct point {
    int address;
    int num;
};

int head_point_address;
int n;
int address[maxn][2];
set<int> vis;
vector<point> del;

int main() {
    mem(address, -1);
    cin >> head_point_address >> n;
    for (int i = 0; i < n; ++i) {
        int input_address, input_num, input_next_address;
        cin >> input_address >> input_num >> input_next_address;
        address[input_address][0] = input_num;
        address[input_address][1] = input_next_address;
    }
    int add_temp = head_point_address;
    printf("%05d %d ", add_temp, address[add_temp][0]);
    vis.insert(abs(address[add_temp][0]));
    add_temp = address[add_temp][1];
    while (add_temp != -1) {
        int judge_temp = abs(address[add_temp][0]);
        if (vis.count(judge_temp) != 0) {
            point add;
            add.address = add_temp;
            add.num = address[add_temp][0];
            del.push_back(add);
        }
        else {
            printf("%05d\n%05d %d ", add_temp, add_temp, address[add_temp][0]);
            vis.insert(judge_temp);
        }
        add_temp = address[add_temp][1];
    }
    cout << -1 << endl;
    if (del.size() != 0) {
        vector<point>::iterator it = del.begin();
        point show_start = *it;
        printf("%05d %d ", show_start.address, show_start.num);
        it++;
        for (; it != del.end(); ++it) {
            point show = *it;
            printf("%05d\n%05d %d ", show.address, show.address, show.num);
        }
        cout << -1;
    }
    return 0;
}