2020-11-09 12:10:06

#### The main idea of the topic :

The existing length is N, Starting from `begin_address` The single chain table of , Ask for every K Inverse the nodes , In the end, it's not enough K We don't need to invert , It is required to output the single linked list completed by the last inversion .

#### Algorithm ideas ：

Here we use the method of simulating the inversion of single linked list , We use `node` Array stores all input nodes ,`result` Store the single linked list after the last inversion . For the inversion of single linked list, we should think of the head insertion method , So, first of all, we did it for `result` The linked list creates a head node , Here, the address of the head node must not be in the input list , So I chose 100004 As a header address . Then calculate the number of nodes in the list that need to be reversed , Use `group` Variable to hold the , For each group , We use the header insertion method to insert into the new linked list `result` in , That's it K Inverse of nodes , At the same time, in order to update the position of the head node , We use `tail` To mark `result` The position of the tail node , Update to the address of the inserted node at the first insertion . In this way, after each group is inserted, the position of the head node is updated to `tail`, And so on , After all the nodes of the group are inserted into `result` In the list . Finally, judge whether there are any remaining nodes , If there is , Then insert it into `result` In the list , Then output the new linked list from the next node of the first node .

#### Be careful ：

1、 about PAT It is possible that the data entered is invalid , Especially the single chain list , So we have to go through the list first , Count the number of effective nodes in the linked list `count`( The number of nodes in the input single chain list ), The purpose is to calculate the number of groups of inverses `group`.
2、 Because the address given by the title is 5 Digit number , The output must also be guaranteed to be 5 digit , except -1 exception .
3、 The way to determine whether there are any remaining insertion nodes is `work_n` Is it equal to -1, Because it is equal to -1 It indicates that the nodes of all groups arrive at the empty node after insertion , There can't be any more nodes
4、 about `result` The acquisition of linked list , You have to create a new node p, And then update p And then insert it into `result` in , Don't update directly `result` The address of , such as `result[work_n].address = work_n`, because `result[work_n]` It's a node , No nodes are added to the linked list , How to record address information ？
5、 You can use to create `address` And `data`,`address` And `next` The mapping relation of , Directly reverse `address`, Then it next For the last node `address` To deal with it , But it doesn't directly reverse the single chain list ( Easy to think of ).

#### Submit results ： #### AC Code ：

``````#include <cstdio>

using namespace std;

struct Node{
int data;
int next;
}node,result;

int main(){
Node n{};//  Hold every node of input
for (int i = 0; i < N; ++i) {
}
//  Count the number of valid nodes in the input linked list
int count = 0;
int work_n = begin_address;// Working in node The pointer on the linked list
while (work_n!=-1){
++count;
work_n = node[work_n].next;
}
//  Calculate the number of groups that can be reversed
int group = count/K;
//  establish result The head node of the list
//  For each node of each group, it is inserted into result Go to the list
int tail = -1;//result The tail pointer of , Point to the last node
for (int i = 0; i < group; ++i) {
for (int j = 0; j < K; ++j) {
Node p{work_n, node[work_n].data, result[begin].next};
work_n = node[work_n].next;//  Point to the next node location
if(j==0){
}
}
//  The head node is updated after each set of nodes is inverted
begin = tail;
}
while (work_n!=-1){
//  And then there are some nodes that don't need to be inverted , Insert it into the linked list by tail insertion
Node p{work_n, node[work_n].data, -1};
begin = result[begin].next;//  Point to result Next node location
work_n = node[work_n].next;//  Point to node Next node location
}
for(begin = result.next;begin!=-1;begin = result[begin].next){
if(result[begin].next==-1){
} else {
}
}
return 0;
}
``````