Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤) which is the total number of nodes, and a positive K (≤) which is the size of a block. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218
Sample Output:
71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1题意：
链表的转置。给定N和K，每K个转一转，最后还要整个再转一转。
题解：
这道题挺熟悉的，和1074 Reversing Linked List (25分)差不多嘛。
当时依稀记得，用vector超方便，但是忘了怎么用
reverse(valid.begin()+i*k,valid.begin()+i*k+k);
然后就十分痛苦地用不了现成的reverse，只好把开两个vector当成数组用，然后非常艰难地写完了。。。。
AC代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int d;
int id;
int nx;
}a[],b[];
vector<node>v;
int main(){
int n,k;
int root;
cin>>root>>n>>k;
for(int i=;i<=n;i++){
int x,y,z;
cin>>x>>z>>y;
a[x].d=z;
a[x].nx=y;
a[x].id=x;
}
node nroot=a[root];
v.push_back(nroot);
int num=;
while(nroot.nx!=-){//先按照链表的顺序存好放到vector中
nroot=a[nroot.nx];
v.push_back(nroot);
num++;
}
int cs=num/k;//cs表示要转几次
for(int i=;i<cs;i++){
for(int j=;j<k;j++){
a[i*k+j]=v.at(i*k+k-j-);//每k个转一转，本来可以 reverse(v.begin()+i*k,v()+i*k+k);唉。。。
}
}
int pp=cs*k-;
if(cs*k<num){//剩下的不到K个也要转
for(int i=v.size()-;i>=cs*k;i--) a[++pp]=v.at(i);
}
for(int i=;i<num;i++){//再整个链表转一下，本来可以reverse(v.begin(),v.end())的,唉。。。
b[i]=a[num-i-];
}
for(int i=;i<num;i++){//修改b数组里每个结构体的nx值
if(i!=num-) b[i].nx=b[i+].id;
else b[i].nx=-;
}
for(int i=;i<num-;i++){//输出
printf("%05d %d %05d\n",b[i].id,b[i].d,b[i].nx);
}
printf("%05d %d -1",b[num-].id,b[num-].d);
return ;
}