PAT A1074 Reversing Linked List

这道题极其经典，链表反转今年考研的时候也出现过。所以是重点的重点，以后要做双向链表的反转；

最主要的是观察反转链表中的规律变化。这里贯穿一个特别重要的思想，就是有用的链表节点放在左边，方便进行访问，解决了节点从后往前遍历的问题，所以就可以从后向前按照坐标进行后继的修改。当时自己就卡在这个地方，所以这是最重要的两个点之一。

#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=100010;
struct Node{
    int address=0;
    int next=0;
    int data=0;
    int order;
}node[MAXN];
bool cmp(Node a,Node b){
    return a.order<b.order;
}
int main(){
    for(int i=0;i<MAXN;i++){
        node[i].order=MAXN;
    }
    int start_address,num,group,address;
    scanf("%d%d%d",&start_address,&num,&group);
    for(int i=0;i<num;i++){
        scanf("%d",&address);
        scanf("%d%d",&node[address].data,&node[address].next);
        node[address].address=address;
    }
    int p=start_address,count=0;
    while(p!=-1){
        node[p].order=count++;
        p=node[p].next;
    }
    sort(node,node+MAXN,cmp);
    num=count;
    for(int i=0;i<num/group;i++){
        //按组数
        for(int j=(i+1)*group-1;j>i*group;j--){
            printf("%05d %d %05d\n",node[j].address,node[j].data,node[j-1].address);
        }
        printf("%05d %d ",node[i*group].address,node[i*group].data);
        if(i<num/group-1){
            printf("%05d\n",node[(i+2)*group-1].address);
            //如果不是最后一块，则指向下一个节点的首地址
        }else{
            if(num%group==0){
                printf("-1\n");
            }else{
                printf("%05d\n",node[(i+1)*group].address);
                for(int i=num/group*group;i<num;i++){
                    printf("%05d %d ",node[i].address,node[i].data);
                    if(i<num-1){
                        printf("%05d\n",node[i+1].address);
                    }else{
                        printf("-1\n");
                    }
                }
            }
        }
    }
    system("pause");
    return 0;
}