PAT 1052 Linked List Sorting [一般]

1052 Linked List Sorting （25 分）

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive

Then

Address Key Next

where Address is the address of the node in memory, Key is an integer in [

Output Specification:

For each test case, the output format is the same as that of the input, where

Sample Input:

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

Sample Output:

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

题目大意：给出一个链表，按照其中存储的key值大小重新排序。

最终AC:

#include <iostream>
#include <algorithm>
#include<cstdio>
#include <vector>
using namespace std;

struct Node{
    int now,num,next;
}node[100010];
vector<Node> vt;
bool cmp(Node& a,Node& b){
    return a.num<b.num;
}
int main()
{
    int n,f;
    scanf("%d%d",&n,&f);
    int t,num,next;
    for(int i=0;i<n;i++){
        cin>>t>>num>>next;
        node[t].num=num;
        node[t].next=next;
        node[t].now=t;
    }
    for(int index=f;index!=-1;index=node[index].next){
        vt.push_back(node[index]);
    }

    //有一个疑问就是如果输入数据为0 0 ，怎么输出？
    if(vt.size()==0){
        printf("0 -1");
    }else{
        sort(vt.begin(),vt.end(),cmp);
        printf("%d %05d
",vt.size(),vt[0].now);
    for(int i=0;i<vt.size();i++){
        if(i!=vt.size()-1){
            printf("%05d %d %05d
",vt[i].now,vt[i].num,vt[i+1].now);
        }else{
            printf("%05d %d -1",vt[i].now,vt[i].num);
        }
    }
    }
    return 0;
}

//自己遇到了很多坑。。。

1.对于输入是0 0不知道如何输出，看了别人的发现是输出0和-1，记住吧，以后对于链表长度为0的，就是输出数量0，然后直接就是结束-1.

2.第一次提交时有段错误，感觉到是数组定义长度的问题，一开始定义长度为100000，后来又加了10可以了，最后一个测试点，那么以后在定义时就比平常多加10就可以啦

3.之后提交发现第4个测试点过不去，这是为什么呢？去牛客网上发现是如下错误：

测试用例:
1 00000
00000 5 -1

对应输出应该为:

1 00000
00000 5 -1

你的输出为:

1 0

最终在输出起点坐标时加上了%05d，就可以了。。。。