题目

时间限制
300 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN, Yue
给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

分析：

拿到题目我们不知道如何下手，先把这个链表排回去吧

对比上面的输出样例，中间最明显的数据部分，1~4逆序了，但是它们的第一个结点位置并未改变；再观察，可以发现，逆序的部分的下一结点位置也随之改变，且和下一行的结点位置相等，所以其实我们可以用同一个数组来保存。

我们先定义两个数组，一个存结点，一个存数据。
数组存储可以用两种方法：
1.从0~n存值，
2.根据第一个输入的结点位置为索引，存值
分别考虑1和2的情况，如果用1，每次结点位置的变化，我们得”带”着数组一起变，而如果是2，我们只需要按照结点位置索引，即可找到该位置的值或该位置的结点位置。所以我们用2方法存值。

既然要逆转链表，显而易见，直接对结点数组和数据数组进行操作，不易实现，我们考虑再开一个数组，来对这两个数组进行索引，逆转直接对索引逆转即可。

代码(cpp)

#include<iostream>
#include<algorithm>
using namespace std;
int dat[100005];
int nex[100005];
int lis[100005];
int main(){
    int first,n,k;
    cin>>first>>n>>k;
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        cin>>dat[temp]>>nex[temp];
    }
    int sum=0;
    while(first!=-1){   //把索引数组理出来
        lis[sum++] = first;
        first = nex[first];
    }
    for(int i=0;i<sum-sum%k;i+=k)  //反转索引
        for(int j=0;j<k/2;j++){
            int t = lis[i+j];
            lis[i+j] = lis[i+k-j-1];
            lis[i+k-j-1] = t;
        }
    for(int i=0;i<sum-1;i++)
        printf("%05d %d %05d\n",lis[i],dat[lis[i]],lis[i+1]);
    printf("%05d %d -1",lis[sum-1],dat[lis[sum-1]]);
    return 0;
}