7-2 Block Reversing (25分)
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.
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.
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.
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
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[100005],b[100005]; vector<node>v; int main(){ int n,k; int root; cin>>root>>n>>k; for(int i=1;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=1; while(nroot.nx!=-1){//先按照链表的顺序存好放到vector中 nroot=a[nroot.nx]; v.push_back(nroot); num++; } int cs=num/k;//cs表示要转几次 for(int i=0;i<cs;i++){ for(int j=0;j<k;j++){ a[i*k+j]=v.at(i*k+k-j-1);//每k个转一转，本来可以 reverse(v.begin()+i*k,v()+i*k+k);唉。。。 } } int pp=cs*k-1; if(cs*k<num){//剩下的不到K个也要转 for(int i=v.size()-1;i>=cs*k;i--) a[++pp]=v.at(i); } for(int i=0;i<num;i++){//再整个链表转一下，本来可以reverse(v.begin(),v.end())的,唉。。。 b[i]=a[num-i-1]; } for(int i=0;i<num;i++){//修改b数组里每个结构体的nx值 if(i!=num-1) b[i].nx=b[i+1].id; else b[i].nx=-1; } for(int i=0;i<num-1;i++){//输出 printf("%05d %d %05d\n",b[i].id,b[i].d,b[i].nx); } printf("%05d %d -1",b[num-1].id,b[num-1].d); return 0; }
PAT-2019年冬季考试-甲级 7-2 Block Reversing (25分) (链表转置)
原文：https://www.cnblogs.com/caiyishuai/p/12005390.html