PAT 1074. Reversing Linked List (25)

Posted on Edited on In

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.

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 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:

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

Sample Output:

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

给定一个链表，每K个翻转一下，最后输出。 给定的地址都是5位数的，可以开一个10w的数组，通过数组索引可以很方便的找到结点的下一个结点，调用reserse方法可以将指定的地址进行逆序翻转，最后得到翻转后的链表，格式化输出。 代码如下：

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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    int address, data, next;
};

int main() {
    int head = 0, n = 0, k = 0;
    scanf("%d %d %d", &head, &n, &k);
    vector<struct Node> v(100000);
    for (int i = 0; i < n; i++) {
        struct Node node;
        scanf("%d %d %d", &node.address, &node.data, &node.next);
        v[node.address] = node;
    }

    vector<struct Node> nodes;
    for (int i = 0; head != -1; i++) {
        nodes.push_back(v[head]);
        head = v[head].next;
    }

    k = k > nodes.size() ? k % nodes.size() : k;
    for (int i = 0; i <= nodes.size() - k; i += k) {
        reverse(nodes.begin() + i, nodes.begin() + i + k);
    }

    for (int i = 0; i < nodes.size(); i++) {
        if (i != nodes.size() - 1) {
            printf("%05d %d %05d\n", nodes[i].address, nodes[i].data, nodes[i + 1].address);
        } else {
            printf("%05d %d -1\n", nodes[i].address, nodes[i].data);
        }
    }
    return 0;
}