Home PAT 1052 Linked List Sorting
Post
Cancel

PAT 1052 Linked List Sorting

Link

最后一个测试点: linkList 是空的, 即: 根本没有给出头节点. 那么头节点就是 -1. 因此这种情况应该输出 0 -1 !

还有就是, 这种链表的题都要注意: 并不是给出的每一个地址都在链表中的, 需要根据头节点找一遍.

如果不判断链表节点数为 0 的情况, 那么最后一个测试点就是“段错误”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,head;
struct node{
    int addr,key,next;
    bool operator<(node x)const{
        return key<x.key;
    }
}nodes[100010];
vector<node>linkList;
int main() {
    scanf("%d%d",&n,&head);
    for(int i=1;i<=n;++i){
        int addr,key,next;
        scanf("%d%d%d",&addr,&key,&next);
        nodes[addr]={addr,key,next};
    }
    int p=head;
    while(p!=-1){
        linkList.push_back(nodes[p]);
        p=nodes[p].next;
    }
    if(linkList.size()==0){
        printf("0 -1\n");
        return 0;
    }
    sort(linkList.begin(),linkList.end());
    printf("%d %05d\n%05d %d",linkList.size(),linkList[0].addr,linkList[0].addr,linkList[0].key);
    for(int i=1;i<linkList.size();++i)
        printf(" %05d\n%05d %d",linkList[i].addr,linkList[i].addr,linkList[i].key);
    printf(" -1\n");
    return 0;
}
This post is licensed under CC BY 4.0 by the author.