PAT A1097 Deduplication on a Linked List

这道题的大致意思是给出一个链表，剔除其中的绝对值相等的重复元素，并且将重复元素和剔除后的链表进行输出。

本来原来的思路是维持两个链表，将重复的和不重复的单独提出加入链表，但是这种方法极其麻烦。

书上给的思路十分值得借鉴，和之前总结的链表题目一样，将每个链表节点中标志一个order位，然后对整体进行排序，使得有效节点全部在链表左边。并且其中，不重复的左半部分，重复的在右半部分。

然后按照顺序输出，这样输出的有一个好处就是不需要像之前自己想的方法那样考虑前驱后继节点值的改变，只需要按照顺序就行相应的输出该表就可以。

这个解法又彰显了有效节点排序的思想；

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn=100005;
const int TABLE=1000010;
struct Node{
    int address,data,next;
    int order;
}node[maxn];
bool isExist[TABLE]={false};
bool cmp(Node a,Node b){
    return a.order<b.order;
}
int main(){
    for(int i=0;i<maxn;i++){
        node[i].order=2*maxn;
    }
    int n,begin,address;
    scanf("%d%d",&begin,&n);
    for(int i=0;i<n;i++){
        scanf("%d",&address);
        scanf("%d%d",&node[address].data,&node[address].next);
        node[address].address=address;
    }
    int countValid=0,countRemoved=0,p=begin;
    while(p!=-1){
        if(!isExist[abs(node[p].data)]){
            isExist[abs(node[p].data)]=true;
            node[p].order=countValid++;
        }else{
            node[p].order=maxn+countRemoved++;
        }
        p=node[p].next;
    }
    sort(node,node+maxn,cmp);
    int count=countValid+countRemoved;
    for(int i=0;i<count;i++){
        if(i!=countValid-1&&i!=count-1){
            printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
        }else{
            printf("%05d %d -1\n",node[i].address,node[i].data);
        }
    }
    system("pause");
    return 0;
}