链表去重
时间限制: 400 ms
内存限制: 64 MB
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤10^5，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。
随后 N 行，每行按以下格式描述一个结点：
其中地址是该结点的地址，键值是绝对值不超过10^4的整数，下一个结点是下个结点的地址。
输出格式：
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。
输入样例:
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
|
代码
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
49
50
51
52
53
54
| #include <stdio.h>
#include <stdlib.h>
struct node
{
int val;
int next;
} ram[100005];
int exist[100005] = {0};
int main()
{
int start, n, addr, val, next;
scanf("%d%d", &start, &n);
for(int i = 0; i < n; ++i)
{
scanf("%d%d%d", &addr, &val, &next);
ram[addr].val = val;
ram[addr].next = next;
}
int a[n], na = 1, b[n], nb = 0;
a[0] = start;
exist[abs(ram[start].val)] = 1;
for(int i = ram[start].next; i != -1; i = ram[i].next)
{
if(!exist[abs(ram[i].val)])
{
exist[abs(ram[i].val)]++;
a[na++] = i;
}
else
b[nb++] = i;
}
for(int i = 0; i < na; ++i)
{
printf("%05d %d ", a[i], ram[a[i]].val);
if(i == na-1)
printf("-1\n");
else
printf("%05d\n", a[i+1]);
}
for(int i = 0; i < nb; ++i)
{
printf("%05d %d ", b[i], ram[b[i]].val);
if(i == nb-1)
printf("-1\n");
else
printf("%05d\n", b[i+1]);
}
return 0;
}
|