1074 Reversing Linked List

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

题意

第一行给定链表起始结点的地址 h、总结点数量 n 和一个常数 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 。如果剩余的结点数不满 k 个，则不需要进行反转。

另外，没有出现在链表中的结点不需要考虑。

思路

具体思路如下：

1.先将每个结点的数据以及其指向下一个结点的地址用数组 data 和 ne 存起来，方便后续调用。

2.用一个数组 q 将链表中的所有结点地址存进来，这样也可以排除那些不在链表内的结点。

3.对每 k 个接点进行反转，不满 k 个的结点不需要反转。

4.输出反转后的结果，注意最后一个结点的下一个地址是 -1 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h, n, k;
int e[N], ne[N];
int main()
{
    //输入每个结点的信息
    cin >> h >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int address, data, next;
        scanf("%d %d %d", &address, &data, &next);
        e[address] = data, ne[address] = next;
    }
    //将链表中的结点地址存入数组中
    vector<int> q;
    for (int i = h; i != -1; i = ne[i])  q.push_back(i);
    //每k个元素就进行一个反转
    for (int i = 0; i + k - 1 < q.size(); i += k)
        reverse(q.begin() + i, q.begin() + i + k);
    //输出反转后的结果
    for (int i = 0; i < q.size(); i++)
    {
        printf("%05d %d ", q[i], e[q[i]]);
        if (i + 1 == q.size())   puts("-1");
        else    printf("%05d\n", q[i + 1]);
    }
    return 0;
}