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

原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1074

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:

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个进行反转。

首行三个值为首地址，节点数，K值。而后N行为第i个节点的所在地址，值，下一地址。

解题报告

存储每个节点的状态，并记录下一个地址。

注意事项：

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"<<endl;
        else
            printf("%05d\n",link[next]);

    }
    system("pause");
}