1165 Block Reversing – PAT甲级真题

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 (≤105) 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

题目大意：给定一个单链表L，将每K个结点看成一个区块（链表最后若不足K个结点，也看成一个区块），请编写程序将L中所有区块的链表反转。例如：给定L为1→2→3→4→5→6→7→8，K为3，则输出应该为7→8→4→5→6→1→2→3。每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(≤10的五次方)、以及正整数K(≤N)，即区块的大小。结点的地址是5位非负整数，NULL 地址用−1表示。接下来有N行，每行格式为：Address Data Next，其中Address是结点地址，Data是该结点保存的整数数据，Next是下一个结点的地址。对于每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
分析：L为输入链表，ans为答案链表，二维数组E为区块链表。先将链表数据记录在结构体A中，遍历A将链表正确顺序记录在链表L中，然后需要重新定义链表长度n（因为有输入中有无效的假结点信息）。遍历链表L，将每K个结点所分隔成的区块保存在二维数组E中，再从后往前将区块链表E中的值添加到答案链表ans中，最后根据格式输出ans链表就好啦~

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}A[100001];
vector<int> L, ans, E[100001];
int s, n , a, t, k, mark, cnt, c;
int main() {
    cin >> s >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a;
        cin >> A[a].data >> A[a].next;
    }
    t = s;
    while (t != -1) {
        L.push_back(t);
        t = A[t].next;
    }
    n = L.size();
    for (int i = 0; i < n; i++) {
        E[c].push_back(L[i]);
        cnt++;
        if (cnt == k && i != n - 1) {
            cnt = 0;
            c++;
        }
    }
    for (int i = c; i >= 0; i--)
        for (auto it : E[i]) 
            ans.push_back(it);
    for (int i = 1; i < n; i++) 
        printf("%05d %d %05d\n", ans[i - 1], A[ans[i - 1]].data, ans[i]);
    printf("%05d %d -1", ans.back(), A[ans.back()].data);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int data, next;

}A[100001];

vector<int> L, ans, E[100001];

int s, n , a, t, k, mark, cnt, c;

int main() {

cin >> s >> n >> k;

for (int i = 0; i < n; i++) {

cin >> a;

cin >> A[a].data >> A[a].next;

}

t = s;

while (t != -1) {

L.push_back(t);

t = A[t].next;

}

n = L.size();

for (int i = 0; i < n; i++) {

E[c].push_back(L[i]);

cnt++;

if (cnt == k && i != n - 1) {

cnt = 0;

c++;

}

for (int i = c; i >= 0; i--)

for (auto it : E[i])

ans.push_back(it);

for (int i = 1; i < n; i++)

printf("%05d %d %05d\n", ans[i - 1], A[ans[i - 1]].data, ans[i]);

printf("%05d %d -1", ans.back(), A[ans.back()].data);

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版