[pta]L2-002 链表去重

L2-002 链表去重

分数 25

作者 陈越

单位 浙江大学

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

输入格式：

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

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

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

输出格式：

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

输入样例：

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

我的想法：

我的想法很直接，既然地址这东西是唯一的，而且都是五位数，直接先开两个数组key和nxt来存储链表的键值和下一个地址，而这两个的数组的下标就用相应的当前的地址就行了

然后开一个list来顺序整理当前的地址

然后再开一个keep和dei，一个顺序记录去重后的地址，一个顺序记录键值重复的地址，开一个vs数组来记录键值是否重复

遍历list，不是重复的就放进keep，是重复的就放进del

输出这一步比较关键，把当前地址和键值看做一个整体，一起输出，至于下一个地址，显然，和下一行（如果有的话）的当前地址一致，那么直接输出keep[i+1]或者del[i+1]就行了，这样就不用考虑已修改原本存的下一个地址了

代码如下

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int key[N], nxt[N], n, head; int main() { cin >> head >> n; for (int i = 0; i < n; i++) { int add; cin >> add; cin >> key[add] >> nxt[add]; } vector<int>list; for (int p = head; p != -1; p = nxt[p]) { list.push_back(p); } vector<int>keep, del; int vs[N] = { 0 }; for (auto add : list) { int abskey = abs(key[add]); if (!vs[abskey]) { keep.push_back(add); vs[abskey] = 1; } else del.push_back(add); } for (int i = 0; i < keep.size(); i++) { printf("%05d %d ", keep[i], key[keep[i]]); if (i == keep.size() - 1)printf("-1\n"); else printf("%05d\n", keep[i + 1]); } for (int i = 0; i < del.size(); i++) { printf("%05d %d ", del[i], key[del[i]]); if (i == del.size() - 1)printf("-1\n"); else printf("%05d\n", del[i + 1]); } return 0; }