PAT-A 1074 Reversing Linked List (25)

Given a constant $K$ and a singly linked list L, you are supposed to reverse the links of every $K$ elements on $L$. For example, given L being 1→2→3→4→5→6, if $K=3$, then you must output 3→2→1→6→5→4; if $K=4$, you must output 4→3→2→1→5→6.

Problem: PAT-A 1074 Reversing Linked List

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(≤10^5)$ which is the total number of nodes, and a positive $K(≤N)$ which is the length of the sublist to be reversed. 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

1
2
3
4
5
6
7

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

Sample Output

1
2
3
4
5
6

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

Analysis

  题目大意：给一个链表，每 $K$ 个结点翻转一次，即倒着输出这 $K$ 个结点。不足 $K$ 个结点的部分不反转。

  注意输入的结点可能不全在链表上，所以按照地址遍历一遍把结点放入 vector。然后遍历 vector，每次取 $K$ 个结点并反向输出。不需要修改 next，直接输出下一结点的地址，详情见代码。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    string addr, next;
};

unordered_map<string, Node> mp;

int main() {
    string fst;
    fst.resize(10);
    int N, K;
    scanf("%s %d %d", &fst[0], &N, &K);
    Node t;
    t.addr.resize(10);
    t.next.resize(10);
    while (N--) {
        scanf("%s %d %s", &t.addr[0], &t.val, &t.next[0]);
        mp[t.addr] = t;
    }
    vector<Node> v;
    while (fst[0] != '-') {
        v.push_back(mp[fst]);
        fst = mp[fst].next;
    }
    int len = v.size(), flag = 0;
    for (int i = 0; (i + 1) * K <= len; i++) {
        for (int j = (i + 1) * K - 1; j >= i * K; j--) {
            if (flag) printf("%s\n%s %d ", v[j].addr.c_str(), v[j].addr.c_str(), v[j].val);
            else printf("%s %d ", v[j].addr.c_str(), v[j].val);
            flag++;
        }
    }
    for (int i = len - len % K; i < len; i++) {
        if (flag) printf("%s\n%s %d ", v[i].addr.c_str(), v[i].addr.c_str(), v[i].val);
        else printf("%s %d ", v[i].addr.c_str(), v[i].val);
        flag++;
    }
    printf("-1\n");
}

Tsukkomi

  19 年年底考乙级的前一天临时抱佛 jio 刷到这题的兄弟，当时被卡到怀疑人生然后放弃，生怕第二天考试遇到类似的题。结果考试时的最后一题真的就是那道改的，当时一个劲调整心态，希望前一天没过的题今天能搞出来。记得是只有一个测试点过不去，当时还不怎么熟悉 STL，单纯地写成了链表并且修改每个结点的 next。写到最后十几分钟抱着试一试的心态改成按地址输出，交上去顺利拿到满分！当时又开心又惭愧，开心是乙级划水顺利拿到满分，松了口气；惭愧是觉得自己思维还太局限，能力还差得远。总之，继续加油！