[PAT解题报告] Deduplication on a Linked List

PAT的链表题，表示链表的方法很诡异，类似的表示还有1052， 1074。也不难，本题给定一个存储整数的链表，只保存每种绝对值第一次出现的节点，同一个绝对值第二次及以后的出现都扔掉，保留的节点和扔掉的节点分别组成两个小链表。

链表存放整数的绝对值不超过10000，所以可以用bool数组或者bitmap保存某个绝对值在之前是否出现过。

不知道有没有极端情况，输入的链表就是个空的……

总之，我们可以先新建立两个表头h1, h2 和表尾t1, t2，初始都是空的，表示我们最后保留的链表和过滤掉的链表。链表的优势就是对每个节点可以单独折腾……

我们对原始链表里每个节点，可以通过我们那个bool数组判断这个绝对值是否出现过，如果出现过就接到第二个链表末尾，否则就放到第一个链表的末尾。接在链表末尾的操作注意和用指针差不多，注意是否是第一个表头节点，同时别忘更新最后一个元素的地址，因为每次都要接在最后一个元素后面……当然接在前面再翻转一次也是可以的。

最后输出也要注意链表为空的情况，还有注意最后一个位置的next是-1。

难度不大，就是每种细节的处理而已。

代码：

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

int Next[1000000];
int a[1000000];
bool mark[10005];

int main() {
int n;
int head;
    for (scanf("%d%d",&head,&n);n;--n) {
        int x;
        scanf("%d",&x);
        scanf("%d%d",a + x, Next + x);
    }
    int h1 = -1, h2 = -1, t1 = -1, t2 = -1;
    for (; head >= 0; head = Next[head]) {
        int x = (a[head] >= 0)?a[head]:(-a[head]);
        if (mark[x]) {
            if (t2 < 0) {
                h2 = t2 = head;
            }
            else {
                t2 = Next[t2] = head;
            }
        }
        else {
            mark[x] = true;
            if (t1 < 0) {
                h1 = t1 = head;
            }
            else {
                t1 = Next[t1] = head;
            }
        }
    }
    if (t1 >= 0) {
        Next[t1] = -1;
        for (head = h1; head >= 0; head = Next[head]) {
            printf("%05d %d", head, a[head]);
            if (Next[head] >= 0) {
                printf(" %05d\n", Next[head]);
            }
            else {
                puts(" -1");
            }
        }
    }
    if (t2 >= 0) {
        Next[t2] = -1;
        for (head = h2; head >= 0; head = Next[head]) {
            printf("%05d %d", head, a[head]);
            if (Next[head] >= 0) {
                printf(" %05d\n", Next[head]);
            }
            else {
                puts(" -1");
            }
        }
    }
            
    return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1097