A1165 Block Reversing (25 分)

A1165 Block Reversing (25 分)

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个nodes视为一个block（单链表的末尾余下的结点可能会少于K个，仍然把它视为一个block）。

你的任务就是：在链表L中反转这些block，然后输出

思路

1. 把每个block单独存储在一个二维vector<vector<int> >中
2. 然后倒序存入一个一维的vector<int>中，组成一个新的单链表
3. 最后输出

AC代码

#include <bits/stdc++.h>
using namespace std;
int first, n, k;
struct node{
    int address, data, next;
};
unordered_map<int, node> arr;

int main() {
    int address, data, next;
    scanf("%d%d%d", &first, &n, &k);
    for (int i = 0; i < n; ++i) {
        cin >> address >> data >> next;
        arr[address] = node{address, data, next};
    }
    address = first;
    vector<int> block;
    vector<vector<int> > list;
    int cnt = 0;
    while (address != -1) {
        block.emplace_back(address);
        ++cnt;
        if (cnt == k) {
            list.emplace_back(block);
            block = vector<int>();
            cnt = 0;
        }
        address = arr[address].next;
    }
    if (!block.empty()) list.emplace_back(block);
    vector<int> res;
    while (!list.empty()) {
        block = list.back();
        list.pop_back();
        res.insert(res.end(), block.begin(), block.end());
    }
    int len = res.size();
    for (int i = 0; i < len; ++i) {
        printf("%05d %d ", arr[res[i]].address, arr[res[i]].data);
        if (i == len - 1) printf("-1\n");
        else printf("%05d\n", arr[res[i + 1]].address);
    }
    return 0;
}