[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[i1]或者del[i1]就行了这样就不用考虑已修改原本存的下一个地址了代码如下#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]; } vectorintlist; for (int p head; p ! -1; p nxt[p]) { list.push_back(p); } vectorintkeep, 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; }