PAT甲级1097.

目录

A1097

题目

样例

输入:

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

输出:

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

思路和坑点

　　使用数组保存链表，记录结点本身的id，然后使用数组顺序存储链表结点，则输出时，一个链表结点的next便是紧挨着下一个结点的id，需要剔除不属于链表的结点，并顺带筛选分离保存下来和和删除的链表。链表输出时最后一个结点的next=-1，需要特殊处理。
　　坑点:
　　使用数组解题的时候需要过滤数据

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef struct node{
    int id,data,next;
}Node;
void Print(vector<Node> &v){                //打印链表 
    if(v.size()==0) return;
    int i=0;
    for(i;i<v.size()-1;i++)                 //最后一个特殊处理 
        printf("%05d %d %05d\n",v[i].id,v[i].data,v[i+1].id);    //next用下一个结点的id代替 
    printf("%05d %d -1\n",v[i].id,v[i].data);
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    vector<Node> v(MAXN),re,rm;             //v为所有的数据，re为剩余的结点，rm为益处的结点 
    unordered_map<int,bool> mp;             //统计是否出现过该值 
    int head,n;
    scanf("%d%d",&head,&n);
    for(int i=0;i<n;i++){                   //读入所给的所有结点 
        int id;
        scanf("%d",&id); v[id].id=id;
        scanf("%d%d",&v[id].data,&v[id].next);
    }    
    for(int i=head;i!=-1;i=v[i].next){      //筛选结点 
        int temp=abs(v[i].data);
        if(mp.find(temp)==mp.end()){        //如果是第一次出现，保留 
            mp[temp]=true;
            re.push_back(v[i]);
        }
        else                                //否则，删除 
            rm.push_back(v[i]);
    }
    Print(re);                              //分别打印两个链表 
    Print(rm);
    return 0;
}