[PAT解题报告] Linked List Sorting
简单题， 对链表排序。不过它链表给出的方式是，每个节点的地址，内容，和next节点的地址——再给一个头节点的地址。
我采取简单策略，沿着原始链表，按顺序新建一个数组，包含自身的内容和地址，然后对数组按内容关键字排序。
输出的时候注意：
（1） 表头 数组第一个元素的地址
（2） 除了最后一个元素外，next的地址就是它下一个元素的地址。
输出地址用%05d即可。注意空是-1，还有空链表本身的输出。
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
pair<int,int> a[100005];
pair<int,int> b[100005];
int main() {
int n, head;
scanf("%d%d",&n,&head);
for (int i = 0; i < n; ++i) {
int x;
scanf("%d",&x);
scanf("%d%d",&a[x].first,&a[x].second);
}
for (n = 0;head >= 0; head = a[head].second, ++n) {
b[n] = make_pair(a[head].first, head);
}
sort(b, b + n);
printf("%d",n);
if (n == 0) {
puts(" -1");
}
else {
printf(" %05d\n",b[0].second);
for (int i = 0; i < n; ++i) {
printf("%05d %d", b[i].second, b[i].first);
if (i + 1 < n) {
printf(" %05d\n",b[i + 1].second);
}
else {
puts(" -1");
}
}
}
return 0;
}
原题链接：http://www.patest.cn/contests/pat-a-practise/1052
查看9道真题和解析
MDPI公司福利 122人发布