给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。
输入格式:
输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤105,为结点总数)。一个结点的地址是非负的 5 位整数,空地址 NULL 用 -1 来表示。
随后 N 行,每行按以下格式描述一个结点:
其中地址
是该结点的地址,键值
是绝对值不超过104的整数,下一个结点
是下个结点的地址。
输出格式:
首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。
输入样例:
1 2 3 4 5 6
| 00100 5 99999 -7 87654 23854 -15 00000 87654 15 -1 00000 -15 99999 00100 21 23854
|
输出样例:
1 2 3 4 5
| 00100 21 23854 23854 -15 99999 99999 -7 -1 00000 -15 87654 87654 15 -1
|
思路
使用结构体数组来存储链表结构,并使用链表节点的首地址索引;
利用multiset来判断当前数组是否重复,已经存在则将当前节点的首地址存入c数组中,未出现则存入b数组中。
得到b,c数组后,按照连接模式,当前节点的next为下一个节点的首地址输出结果即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include <bits/stdc++.h> using namespace std; const int maxn = 100010; typedef struct node { int data; int next; } Node; Node List[maxn]; int b[maxn], c[maxn]; int cnt1, cnt2, start, n; multiset<int> s; int main() { cin >> start >> n; for (int i = 0; i < n; i++) { int add; cin >> add; cin >> List[add].data >> List[add].next; } for (int i = start; i != -1; i = List[i].next) { if (s.count(abs(List[i].data))) c[cnt2++] = i; else { b[cnt1++] = i; s.insert(abs(List[i].data)); } } for (int i = 0; i < cnt1 - 1; i++) { printf("%05d %d %05d\n", b[i], List[b[i]].data, b[i + 1]); } printf("%05d %d -1\n", b[cnt1 - 1], List[b[cnt1 - 1]]); for (int i = 0; i < cnt2 - 1; i++) { printf("%05d %d %05d\n", c[i], List[c[i]].data, c[i + 1]); } if (cnt2) printf("%05d %d -1\n", c[cnt2 - 1], List[c[cnt2 - 1]].data); return 0; }
|
使用vector如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include <iostream> #include <cmath> #include <vector>
using namespace std; #define MAX_SIZE 100001
struct Node { int add; int data; };
void my_each(const vector<Node> &ret) { for(int i = 0; i < (int)ret.size() - 1; i++) { printf("%05d %d %05d\n", ret[i].add, ret[i].data, ret[i + 1].add); } if(ret.size() > 0) { printf("%05d %d -1\n", ret.back().add, ret.back().data); } }
int main() { int f_add, n; scanf("%d %d", &f_add, &n); int data[MAX_SIZE], next_add[MAX_SIZE]; for(int i = 1; i <= n; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); data[a] = b; next_add[a] = c; } bool book[10001] = {false}; vector<Node> ret1; vector<Node> ret2; while(f_add != -1) { int num = abs(data[f_add]); if(!book[num]) { book[num] = true; ret1.push_back({f_add, data[f_add]}); } else { ret2.push_back({f_add, data[f_add]}); } f_add = next_add[f_add]; } my_each(ret1); my_each(ret2); return 0; }
|