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

输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（$≤10^5$，为结点总数）。一个结点的地址是非负的 $5$ 位整数，空地址 NULL 用 $−1$ 来表示。

随后 $N$ 行，每行按以下格式描述一个结点：
地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过$10^4$的整数，下一个结点是下个结点的地址。

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

输入样例：

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

分析
数据量不大，可以直接用数组模拟链表，地址当做数组下标，考察基本的删除操作和尾插法。

代码

//                              _ooOoo_
//                             o8888888o
//                             88" . "88
//                             (| -_- |)
//                              O\ = /O
//                           ____/`---'\____
//                        .   ' \| |// `.
//                         / \||| : |||// \
//                        / _||||| -:- |||||- \
//                         | | \\ - /// | |
//                       | \_| ''\---/'' | |
//                        \ .-\__ `-` ___/-. /
//                    ___`. .' /--.--\ `. . __
//                  ."" '< `.___\_<|>_/___.' >'"".
//                 | | : `- \`.;`\ _ /`;.`/ - ` : | |
//                    \ \ `-. \_ __\ /__ _/ .-` / /
//           ======`-.____`-.___\_____/___.-`____.-'======
//                              `=---='
//
//           .............................................
//                   佛祖保佑     一发AC     永无BUG
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
PII lian[maxn];
int vis[maxn];

void pri(int root) {
    if(root == -1) return ;
    while(lian[root].second != -1) {
        printf("%05d %d %05d\n",root, lian[root].first,lian[root].second);
        root = lian[root].second;
    }
    printf("%05d %d -1\n",root, lian[root].first);
}

int main(int argc, char const *argv[]) {
    int root1, n;
    cin >> root1 >> n;
    for(int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >>b >>c;
        lian[a].first = b;
        lian[a].second = c;
    }
    int root2 = -1,tail = -1, pre = root1, now = lian[root1].second;
    vis[abs(lian[root1].first)] = 1;
    while(now != -1) {
        if(vis[abs(lian[now].first)] == 1) {
            if(root2 == -1) root2 = tail = now;
            else {
                lian[tail].second = now;
                tail = now;
            }
            lian[pre].second = lian[now].second;
            lian[now].second = -1;
            now = lian[pre].second;
        }
        else {
            vis[abs(lian[now].first)] = 1;
            pre = lian[pre].second;
            now = lian[now].second;
        }
    }
    //puts("------------");
    pri(root1);
    pri(root2);
    return 0;
}