题目描述

给定一个常数 K 和一个单链表 L，请你在单链表上每 K 个元素做一次反转，并输出反转完成后的链表。

如果链表最后一部分不足 K 个元素，则最后一部分不翻转。

例如，假设 L 为 1→2→3→4→5→6，如果 K=3，则你应该输出 3→2→1→6→5→4；如果 K=4，则你应该输出 4→3→2→1→5→6。

输入格式

第一行包含头节点地址，总节点数量 N 以及常数 K。

节点地址用一个 5 位非负整数表示（可能有前导 0），NULL 用 −1 表示。

接下来 N 行，每行描述一个节点的信息，格式如下：

Address Data Next
其中 Address 是节点地址，Data 是一个整数，Next 是下一个节点的地址。

输出格式

将重新排好序的链表，从头节点点开始，依次输出每个节点的信息，格式与输入相同。

输入样例：

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

思路

输入时用单链表存储链表，然后遍历一遍链表，将数据压缩成一维数组，再用reverse对容器每k个元素进行反转

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, k, h, idx;
int link[N], ne[N], e[N];

int main()
{
    cin >> h >> n >> k;
    for(int i = 0; i < n; i ++ )
    {
        int ad, val, next;
        cin >> ad >> val >> next;
        e[ad] = val, ne[ad] = next;
    }

    while(h != -1)
    {
        link[idx ++] = h;
        h = ne[h];
    }
    for(int i = 0; i + k <= idx; i += k) reverse(link + i, link + i + k);
    for(int i = 0; i < idx; i ++ )
    {
        if(i + 1 >= idx) printf("%05d %d -1\n", link[i], e[link[i]]);
        else printf("%05d %d %05d\n", link[i], e[link[i]], link[i + 1]);
    }
    return 0;
}