区块反转
题目描述
给定一个单链表 $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$ 个结点的地址、结点总个数正整数 $N$、以及正整数 $K$,即区块的大小。结点的地址是 $5$ 位非负整数(可能包含前导 $0$),$NULL$ 地址用 $−1$ 表示。
接下来有 $N$ 行,每行格式为:
Address Data Next
其中 Address
是结点地址,Data
是该结点保存的整数数据,Next
是下一结点的地址。
输出格式
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
数据范围
$1 \le K \le N \le 10 ^ 5$
输入样例:
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
正解:链表
思路
存储以第 $1$ 个节点地址为开头的链表,处理出每个区块的头结点,最后倒序输出每个区块。
具体实现
开一个单链表,每当输入 Address Data Next
时,就令 dat[Address] = Data, nxt[Address] = Next
。
while (n --)
{
scanf ("%d%d%d", &x, &y, &z), dat[x] = y;
if (~z) // 如果 Next 不为 NULL
{
nxt[x] = z;
}
}
然后以第 $1$ 个节点为头扫一遍链表,将 $n$ 设为实际链表的长度(因为
本题中可能包含不在单链表中的节点,这些节点无需考虑。
),然后开一个数组存一下每个区块的头节点。
for (hh = h, n = 1; ~nxt[hh]; hh = nxt[hh], n ++); // 一直在 nxt[hh] 不为 NULL 时将节点数量 ++
for (int i = 1; i <= (n - 1) / k + 1; i ++) // (n - 1) / k + 1:= ⌈n / k⌉,即区块数
{
a[i] = h; // 存区块的头结点
// 下一行的目的是跳过当前的整个区块,才方便取下一个区块的头结点
for (int j = 1; j <= k && ~h; j ++, h = nxt[h]); // 重复执行 k 次(h 不能为 NULL),将当前节点变为下一个节点
}
然后倒序输出每个区块即可(这里的实现稍有些麻烦,具体看代码)
AC Code
#include <cstdio>
#include <cstring>
#define N 100005
using namespace std;
int h, hh, n, k, x, y, z, dat[N], nxt[N], a[N];
int main ()
{
scanf ("%d%d%d", &h, &n, &k), memset (nxt, -1, sizeof (nxt));
while (n --)
{
scanf ("%d%d%d", &x, &y, &z), dat[x] = y;
if (~z)
{
nxt[x] = z;
}
}
for (hh = h, n = 1; ~nxt[hh]; hh = nxt[hh], n ++);
for (int i = 1; i <= (n - 1) / k + 1; i ++)
{
a[i] = h;
for (int j = 1; j <= k && ~h; j ++, h = nxt[h]);
}
for (h = a[(n - 1) / k + 1]; ~nxt[h]; h = nxt[h])
{
printf ("%05d %d %05d\n", h, dat[h], nxt[h]);
}
if (n > k)
{
printf ("%05d %d %05d\n", h, dat[h], a[(n - 1) / k]);
}
else
{
printf ("%05d %d -1", h, dat[h]);
}
for (int i = (n - 1) / k; i; i --)
{
for (h = a[i]; nxt[h] != a[i + 1]; h = nxt[h])
{
printf ("%05d %d %05d\n", h, dat[h], nxt[h]);
}
if (i > 1)
{
printf ("%05d %d %05d\n", h, dat[h], a[i - 1]);
}
else
{
printf ("%05d %d -1", h, dat[h]);
}
}
return 0;
}
感谢您的观看!
$$\href {/blog/content/19548/} {\color {MediumSpringGreen} {【暑假每日一题】题解}}$$