[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

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-09 21:15
清华大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-04 23:04
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议