B1025 反转链表 (25分)

/*
题意：给一个链表，然后给出一个K，每K个节点反转一次

解题：
1、定义及静态链表，order表示在链表中的序号，
2、初始化，令order的初值均为maxn，表示初始时所有节点为无效节点
3、由题目给出的链表首地址begi遍历整条链表，并记录每个有效节点在链表中的序号，统计技术有效节点的个数count。
4、对节点进行排序，按节点order从小到大排序
5、输出链表，这个很烦
将n个节点分块n/k块，枚举这些完整的块，从后往前输出节点信息、注意每一个块最后节点next的处理
（1）如果i号块不是最后一个完整快，那么next就是（i+2)*k - 1号节点，也就是（i+1)号块最后一个节点
（2）如果i号块是最后一个块，同样有两种情况
一、如果n%k==0，则说明这是整个单聊表的最后一个节点，输出-1
二、如果n%k不等于0，则说明这个完整快后面还有一点尾巴，那么这个完整块的最后一个节点的next不是下一个块的最后一个，而是这个块的第一个，接下来，从前往后输出即可

learn && wrong:
1、存在无效节点的可能
2、反转链表只改变节点的next地址，不改变本身地址，因此address和data是绑定的
3、%05d的输出格式会让-1出现错误，所以-1要单独输出
4、给order排序很好
5、排序后输出下一个节点，就是【i+1】.adderss就很不错
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;

struct Node{    //定义链表，步骤1
    int address,data,next;
    int order;  //节点在链表上的序号，无效节点为maxn
}node[maxn];

bool cmp(Node a,Node b){
    return a.order < b.order;   //按order从小到大排序
}

int main()
{
    for(int i = 0;i <maxn;i++){ //初始化（步骤2）
        node[i].order = maxn;   //  初始化全部为无效节点
    }

    int begin, n, K, address;
    scanf("%d%d%d", &begin, &n, &K);    //起始地址，节点个数、步长
    for(int i = 0;i < n;i++){
        scanf("%d",&address);
        scanf("%d%d", &node[address].data, &node[address].next);
        node[address].address = address;
    }

    int p = begin, count = 0;   //count计数有效节点的数目

    while(p != -1){ //遍历链表找出单链表的所有效节点（步骤3）
        node[p].order = count++;    //节点在单链表中的序号
        p = node[p].next;  //下一个结点
    }

    sort(node, node + maxn, cmp);   //按单链表从头到尾顺序排列（步骤4）
    //有效节点为前count个节点，为了下面书写方便，因此把count赋给n
    n = count;
    //单链表已经形成，下面是按题目要求的输出（步骤5）
    for(int i = 0;i < n / K;i++){   //枚举完整的n / K 块
        for(int j = (i + 1) * K - 1;j < i * K;j--){ //第i块倒着输出
            printf("%05d %d %05d\n",    node[j].address, node[j].data, node[j - 1].address);
        }

        //下面是每一块的最后一个结点的next地址的处理
        printf("%05d %d ", node[i * K].address, node[i * K].data);
        if(i < n / K - 1){  //如果不是最后一块，就指向下一块的最后一个结点
            printf("%05d\n", node[(i+2) * K - 1].address);
        }else{  //是最后一块时
            if(n % K == 0){ //恰好是最后一个结点，输出-1
                printf("-1\n");
            }else{  //剩下的不完整块按原先的顺序输出
                printf("%05d\n", node[(i + 1) * K].address);
                for(int i = n / K * K;i < n;i++){
                    printf("%05d %d", node[i].address, node[i].data);
                    if(n < -1){
                        printf("%05d\n",node[i+1].address);
                    }else{
                        printf("-1\n");
                    }
                }
            }
        }
    }
    return 0;
}