[数据结构与算法]PAT B1025/A1074 反转链表

PAT里面的链表题似乎都是一个套路…
在结构体中要定义一个flag，来看这个结点是不是在要求的链表中（考虑到无效结点
，要把无效结点放在后面去） 结构体中不仅要保存next地址，还要保存当前地址
然后利用sort函数把读入了的结点聚在一起使用，输出

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct Node
{
    int order,address,data,next;
    bool flag;
}node[maxn];

bool cmp1(struct Node a,struct Node b)
{
    return a.order<b.order;
}

bool cmp2(struct Node a,struct Node b)
{
    return a.order>b.order;
}

int main()
{
    int start,n,k;
    int count=0;
    int address;
    scanf("%d%d%d",&start,&n,&k);
    for(int i=0;i<maxn;i++)
    {
        node[i].order=maxn;
    }

    for(int i=0;i<n;i++)
    {
        scanf("%d",&address);
        scanf("%d%d",&node[address].data,&node[address].next);
        node[address].address=address;
        node[address].flag=false;
    }

    int p=start;
    while(p!=-1)
    {
        node[p].flag=true;
        node[p].order=count;
        count++;
        p=node[p].next;
    }
    sort(node,node+maxn,cmp1);
    int group=count/k;

    for(int i=1;i<=group;i++)
    {
        sort(node+(i-1)*k,node+i*k,cmp2);
    }

    for(int i=0;i<count;i++)
    {
        printf("%05d %d ",node[i].address,node[i].data);
        if(i==count-1)
        {
            printf("-1\n");
        }
        else 
        {
            printf("%05d\n",node[i+1].address);
        }
    }


}