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

思路

链表直接反转会很繁琐，由于本题属于静态链表，所以我们可以这样处理：

1. 把链表写到一个顺序表（数组或向量）里；
2. 对顺序表进行反转；

这样操作会容易得多。
顺序表的反转感觉像是双指针法，就拿样例 K=4 时举例子，序列表现如下：

• 1, 2, 3, 4, 5, 6

• 4, 2, 3, 1, 5, 6

• 4, 3, 2, 1, 5, 6

代码

本题测试点6未通过，可能是有独立于链表的结点。

#include <iostream>
#include <vector>
using namespace std;
typedef struct ndoe_st {
    int addr;
    int data;
    int next;
}node_st;
node_st myList[100001] = {0x0};
#define SWAP_ITEM(A, B) {node_st tmp = A; A = B; B = tmp;}
int main() {
    int START(0), N(0), K(0);
    cin >> START >> N >> K;
    // Read list
    for(int i = 0; i < N; i++) {
        int _addr(0), _data(0), _next(0);
        cin >> _addr >> _data >> _next;
        myList[_addr].addr = _addr;
        myList[_addr].data = _data;
        myList[_addr].next = _next;
    }
    // Copy list to a vector
    vector<node_st> myVec;
    for(int i = START; i >= 0; i = myList[i].next) {
        myVec.push_back( myList[i] );
    }
    // Do reverse operation
    for(int i = 0; i + K <= myVec.size(); i += K) {      // group by group
        for(int j = 0; j < K/2; j++) {                  // inside the group
            SWAP_ITEM( myVec[i+j], myVec[i+K-j-1] );
        }
    }
    // Display result
    for(int i = 0; i < N-1; i++) {
        printf("%05d %d %05d\n", myVec[i].addr, myVec[i].data, myVec[i+1].addr);
    }
    printf("%05d %d -1\n", myVec[N-1].addr, myVec[N-1].data);
    return 0;
}