数据结构考试——链表去重

发表于 | 分类于 | 评论数： | 阅读次数：

链表去重
时间限制: 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 行，每行按以下格式描述一个结点：

1
地址 键值 下一个结点

其中地址是该结点的地址，键值是绝对值不超过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;
}