PAT甲级1052 Linked List Sorting

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805425780670464

题意：

给定一些内存中的节点的地址，值以及下一节点所在地址。

要求对给定的头指针表示的链表进行排序。

思路：

PAT的题目小细节真的很多啊。这道题要注意有可能有的节点是不在头指针链成的链表里的。

所以要先遍历一次链表，然后再排序。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<map>
 4 #include<set>
 5 #include<iostream>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<vector>
 9 #include<cmath> 
10 #include<stack>
11 #include<queue>
12 
13 #define inf 0x7fffffff
14 using namespace std;
15 typedef long long LL;
16 typedef pair<string, string> pr;
17 
18 int n, head;
19 struct node{
20     int key;
21     int nxt;
22 }l[1000005]; 
23 struct num{
24     int add;
25     int key;
26 }tmp[100005];
27 
28 bool cmp(num a, num b)
29 {
30     return a.key < b.key;
31 }
32 
33 int main()
34 {
35     scanf("%d%d", &n, &head);
36     for(int i = 0; i < n; i++){
37         int a;
38         scanf("%d", &a);
39         scanf("%d%d", &l[a].key, &l[a].nxt);
40     }
41     
42     int now = head;
43     int cnt = 0;
44     while(now != -1){
45         tmp[cnt].add = now;
46         tmp[cnt].key = l[now].key;
47         now = l[now].nxt;
48         cnt++;
49     }
50     sort(tmp, tmp + cnt, cmp);
51     if(cnt == 0){
52         printf("0 -1
");
53     } 
54     else{
55         printf("%d %05d
", cnt, tmp[0].add);
56         for(int i = 0; i < cnt - 1; i++){
57             printf("%05d %d %05d
", tmp[i].add, tmp[i].key, tmp[i + 1].add);
58         }
59         printf("%05d %d -1
", tmp[cnt - 1].add, tmp[cnt - 1].key);
60     }
61     
62     return 0;
63 }