PAT 1165 Block Reversing (25分)

原题链接：PAT 1165 Block Reversing (25分) 关键词：链表 整理时间：2020.7.24

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 (≤10⁵​​) which is the total number of nodes, and a positive K (≤N) which is the size of a block. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1. 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

题目大意： 按照要求修改链表并输出

思路： 节点读进结构体数组a，再遍历链表读进v，最后再生成目标链表的顺序res。注意：可能并不是每个点都在链表上的 因此需要遍历一遍。res序号的顺序就是结果链表的顺序

代码：

#include <iostream> #include <vector> using namespace std; const int maxn = 1e7 + 10; int root, n, k; //root起始地址 n结点数 k块的长度 struct node{ int address, data, next; }a[maxn]; vector<node> v, res; int main(){ //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); cin >> root >> n >> k; for(int i = 0; i < n; i ++ ){ int s, b, c; cin >> s >> b >> c; a[s].address = s; a[s].data = b; a[s].next = c; } for(int p = root; p != -1; p = a[p].next){ v.push_back(a[p]); } //具体的翻转部分建议在纸上先模拟 int len = v.size(); int gnum = (len + k - 1 )/k; for(int i = gnum - 1; i >= 0; i--){ int mx = (i + 1) * k > len ? len : (i + 1) * k; for(int j = i*k; j < mx; j++){ res.push_back(v[j]); } } for(int i = 0; i < res.size()-1; i ++ ) printf("%05d %d %05d\n", res[i].address, res[i].data, res[i+1].address); printf("%05d %d -1", res[res.size()-1].address, res[res.size()-1].data); return 0; }