1110 区块反转 – PAT乙级真题

给定一个单链表 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 (≤105)、以及正整数 K (≤N)，即区块的大小。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

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

分析：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题解离线版