1025 反转链表 (25分)

1025 反转链表 (25分)

#include<stdio.h>
#include<algorithm>
using namespace std;
struct Node{
    int now;
    int data;
    int next;
    int order;
}node[100010];
bool cmp(Node a,Node b){
    return a.order<b.order;
}
int main(){
    int first,n,m;
    scanf("%d%d%d",&first,&n,&m);
    for(int i=0;i<=100010;i++){
        node[i].order=100010;
    }
    for(int i=1;i<=n;i++){
        int now;
        scanf("%d",&now);
        scanf("%d%d",&node[now].data,&node[now].next);
        node[now].now=now;
    }
    int p=first,count=0;
    while(p!=-1){
        node[p].order=count++;
        p=node[p].next;
    }
    sort(node,node+100010,cmp);
    n=count;//有效节点数;
    int k;
    for(int i=0;i<n/m;i++){
        for(int j=(i+1)*m-1;j>i*m;j--){
            printf("%05d %d %05d\n",node[j].now,node[j].data,node[j-1].now);
        }
        if(i<n/m-1){
            printf("%05d %d %05d\n",node[i*m].now,node[i*m].data,node[(i+2)*m-1].now);
        }else{
            if(n%m==0)
                printf("%05d %d -1\n",node[i*m].now,node[i*m].data);
            else{
                printf("%05d %d %05d\n",node[i*m].now,node[i*m].data,node[(i+1)*m].now);
                for(k=0;k<n%m-1;k++){
                    printf("%05d %d %05d\n",node[(i+1)*m+k].now,node[(i+1)*m+k].data,node[(i+1)*m+k+1].now);
                }
                printf("%05d %d -1\n",node[(i+1)*m+k].now,node[(i+1)*m+k].data);
            }
        }
    }
    return 0;
}

第一次,参考算法笔记;
难点在于利用order把链表结点排序;
利用now存数组现有地址

上一篇:LeetCode 1025. 除数博弈(动态规划)


下一篇:1025 反转链表 (25分)