PAT甲级1052.

目录

A1052

题目

样例

输入:

5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345

输出:

5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1

思路和坑点

　　将整个链表单独拉出来，放在一个数组中，链表的结点结构体中要记录自己的id，便于最后输出。这里忽略对next指针的处理，因为对一个结点来说，下一个的id就是他的next，直接引用下一个结点的id就好了。
　　坑点
　　特判结点个数为0的情况，提前判定。
　　以上的next处理方法，最后尾指针需要单独处理。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int id,data,next;
}Node;
Node all[100005];
bool cmp(Node a,Node b){
    return a.data<b.data;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,head;
    scanf("%d%d",&n,&head);
    vector<Node> v;
    for(int i=0;i<n;i++){
        int id;
        scanf("%d",&id);
        all[id].id=id;
        scanf("%d%d",&all[id].data,&all[id].next);
    }
    for(int i=head;i!=-1;i=all[i].next)                 //将链表重新整合进一个数组中 
        v.push_back(all[i]);
    sort(v.begin(),v.end(),cmp);                        //按要求排序 
    if(v.size()==0){                                    //特判如果0个有效结点 
        printf("0 -1");
        return 0;
    }
    printf("%d %05d\n",v.size(),v[0].id);                //输出结果 
    int i=0;
    for(i=0;i<v.size()-1;i++){                            //下一个next指针，即后边一个的id 
        printf("%05d %d %05d\n",v[i].id,v[i].data,v[i+1].id);
    } 
    printf("%05d %d -1",v[i].id,v[i].data);
    return 0; 
}