PAT (Advanced) 1097. Deduplication on a Linked List (25)

原题：1097. Deduplication on a Linked List (25)

解题思路：

按题意模拟静态链表操作即可。

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100000 + 5;
const int maxh = 10000 + 5;

int h[maxh];
struct Node
{
    int key;
    int next;
} nodes[maxn];

void printList(int p)
{
    while(p != -1)
    {
        if(nodes[p].next != -1)
            printf("%05d %d %05d\n", p, nodes[p].key, nodes[p].next);
        else
            printf("%05d %d -1\n", p, nodes[p].key);
        p = nodes[p].next;
    }
}

int main()
{
    int s, n;
    while(scanf("%d%d", &s, &n) == 2)
    {
        for(int i = 0; i < n; i++)
        {
            int ad, k, ne;
            scanf("%d%d%d", &ad, &k, &ne);
            nodes[ad].key = k;
            nodes[ad].next= ne;
        }

        memset(h, 0, sizeof(h));
        int p = s, q, r = -1, rs = -1;

        while(p != -1)
        {
            if(!h[abs(nodes[p].key)])
            {
                h[abs(nodes[p].key)] = 1;
                q = p;
            }
            else
            {
                if(r == -1) {rs = p; r = rs;}
                else {nodes[r].next = p; r = p;}

                nodes[q].next = nodes[p].next;
            }
            p = nodes[p].next;
        }

        if(r != -1)
            nodes[r].next = -1;
        nodes[q].next = -1;

        printList(s);
        printList(rs);
    }
    return 0;
}