# PAT(A) 1074. Reversing Linked List (25)

### 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.

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:

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. 题目给出的N不一定就是一条完整的链的节点数，也许有一些节点不在应有的链上。
2. 后N行给出的第二个值不是其标号，值的内容与其在链表中的位置无关。

### 代码

  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 43 44 45 `#include "iostream" using namespace std; int main(){ int list[100005]; int nextList[100005]; int link[100005]; int start; int n,k,sum=0; cin>>start>>n>>k; int add; int data; int nextAdd; for (int i = 0; i < n; i++){ cin>>add>>data>>nextAdd; list[add] = data; nextList[add] = nextAdd; } int i = 0; while(start!= -1){ link[++sum] = start; start = nextList[start]; } int next = k>sum?1:k; for(i = 1; i <= sum; i ++){ printf("%05d %d ",link[next],list[link[next]]); if ((next - 1) / k < sum / k){ next--; if(next % k == 0) next += 2 * k; if(next > sum){ next -= k - 1; } }else next ++; if(next > sum) cout<<"-1"<