当前位置:网站首页>PAT_ Grade A_ 1074 Reversing Linked List

PAT_ Grade A_ 1074 Reversing Linked List

2020-11-09 12:10:06 Qiao Zixin

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 :

image.png

AC Code :

#include <cstdio>

using namespace std;

struct Node{
    int address;
    int data;
    int next;
}node[100005],result[100005];

int main(){
    int begin_address,N,K;
    scanf("%d %d %d",&begin_address,&N,&K);
    Node n{};//  Hold every node of input 
    for (int i = 0; i < N; ++i) {
        scanf("%d %d %d",&n.address,&n.data,&n.next);
        node[n.address] = n;
    }
    //  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 
    Node head{100004,0,-1};
    result[head.address] = head;
    //  For each node of each group, it is inserted into result Go to the list 
    work_n = begin_address;//  Reset work_n
    int begin = head.address;// result The head pointer of 
    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};
            result[begin].next = p.address;
            result[p.address] = p;
            work_n = node[work_n].next;//  Point to the next node location 
            if(j==0){
                tail = p.address;// Update the address of the tail node 
            }
        }
        //  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};
        result[begin].next = p.address;
        result[p.address] = p;
        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[100004].next;begin!=-1;begin = result[begin].next){
        if(result[begin].next==-1){
            printf("%05d %d -1\n",result[begin].address,result[begin].data);
        } else {
            printf("%05d %d %05d\n",result[begin].address,result[begin].data,result[begin].next);
        }
    }
    return 0;
}

版权声明
本文为[Qiao Zixin]所创,转载请带上原文链接,感谢