1052. Linked List Sorting (25)再

题目连接：https://www.patest.cn/contests/pat-a-practise/1052

这道题也是改了好长时间。注意测试样例中会有节点不再该链表上！另外输出也要分下情况，特殊的是链表为空、root为-1等情况的输出。

其实我的代码中还有不足，就是当N不为空，但是没有在该链表上的节点的时候，没有考虑到这一点，程序会崩溃。虽然能AC……应该是考察到根据链表头找出整个链表即可吧。

 1 #include<stdio.h>
 2 #include<vector>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define MAXN 100005
 6 using namespace std;
 7 
 8 typedef struct Node
 9 {
10     int Address;
11     int Key;
12     int Next;
13 }memory;
14 
15 memory node[MAXN];
16 int cmp(memory a,memory b)
17 {
18     return (a.Key<b.Key);
19 }
20 
21 int main()
22 {
23     int N,root,tmp;
24     scanf("%d %d",&N,&root);
25     vector<memory>head;
26     int i,a,k,n;
27     for (i=0;i<N;i++)
28     {
29         scanf("%d %d %d",&a,&k,&n);
30         node[a].Address=a;
31         node[a].Key=k;
32         node[a].Next=n;
33     }
34     tmp=root;
35     while (tmp>=0)
36     {
37         head.push_back(node[tmp]);
38         tmp=node[tmp].Next;
39     }
40 
41     if (head.empty())
42     {
43         if (root==-1)printf("0 -1
");
44         else printf("0 %05d",root);
45     }
46 
47     else
48     {
49         sort(head.begin(),head.end(),cmp);
50         printf("%d %05d
",head.size(),head[0].Address);
51         int last=head.size()-1;
52 
53         for (i=0;i<=last;i++)
54         {
55             if (i==last)printf("%05d %d -1",head[last].Address,head[last].Key);
56             else
57             {
58                 head[i].Next=head[i+1].Address;
59                 printf("%05d %d %05d
",head[i].Address,head[i].Key,head[i].Next);
60             }
61     }
62     }
63     return 0;
64 }