PAT甲级A1097---链表处理

1097 Deduplication on a Linked List (25分)

分析:

使用data[add]记录地址为add的数的值，nextAdd[add]记录add下一个结点的地址，list数组按顺序记录删掉重复元素后的结点地址，removedList数组按顺序记录删掉的结点的地址。

C++：

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100010;

int data[maxn], nextAdd[maxn], list[maxn], removedList[maxn];
bool isExist[10100];

int main() {
    int begin, n;
    scanf("%d%d", &begin, &n);
    int add;
    for (int i = 0; i < n; i++) {
        scanf("%d", &add);
        scanf("%d%d", &data[add], &nextAdd[add]);
    }
    int cnt1 = 0, cnt2 = 0;
    while (begin != -1) {
        int key = abs(data[begin]);
        if (isExist[key] == false) {
            list[cnt1++] = begin;
            isExist[key] = true;
        } else {
            removedList[cnt2++] = begin;
        }
        begin = nextAdd[begin];
    }
    for (int i = 0; i < cnt1; i++) {
        if (i != cnt1 - 1) {
            printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
        } else {
            printf("%05d %d -1\n", list[i], data[list[i]]);
        }
    }
    for (int i = 0; i < cnt2; i++) {
        if (i != cnt2 - 1) {
            printf("%05d %d %05d\n", removedList[i], data[removedList[i]], removedList[i + 1]);
        } else {
            printf("%05d %d -1\n", removedList[i], data[removedList[i]]);
        }
    }
    return 0;
}