传送门:https://pintia.cn/problem-sets/994805342720868352/problems/994805425780670464

题目大意

给出一个链表,将链表排序,然后把链表上的结点按照data值的从小到大顺序输出


解题思路:

建立结构体数组,按照从首地址开始的顺序(直到-1)遍历一遍整个链表,将在链表中的结点的flag标记为true,并且统计coun t(有效结点的个数)。(因为有的结点根本不在链表中)
然后将链表进行排序,如果flag == false就把他们移动到后面(即:reuturn a.flag > b.flag),最后只输出前count个链表的信息

注意:

最后地址-1的输出要特别处理;

题目可能有无效结点,即不在题目所给出的首地址开始的链表上;

数据还要均为无限结点的情况,需要特判

ac代码:

#include <iostream>
#include <algorithm>
#define maxn 100000
using namespace std;
struct Node{
    int address,data,next;
    bool flag;
}node[maxn];
bool cmp(Node a,Node b)
{
    if(a.flag==false ||b.flag==false )
        return a.flag>b.flag;
    else return a.data<b.data;
}
int main()
{
    for(int i=0;i<maxn;i++)
        node[i].flag=false;
    int n,begin,address;
    scanf("%d%d",&n,&begin);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&address);
        scanf("%d%d",&node[address].data,&node[address].next);
        node[address].address=address;
    }
    int count=0,p=begin;
    while(p!=-1)
    {
        node[p].flag=true;
        count++;
        p=node[p].next;
    }
    if(count==0)
        printf("0 -1");
    else
    {
        sort(node,node+maxn,cmp);
        printf("%d %05d\n",count,node[0].address);
        for(int i=0;i<count;i++)
        {
            if(i!=count-1)
                printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
            else
                printf("%05d %d -1\n",node[i].address,node[i].data);
        }
    }
    return 0;
}