当前位置:网站首页>PAT_ Grade A_ 1097 Deduplication on a Linked List

PAT_ Grade A_ 1097 Deduplication on a Linked List

2020-11-10 14:21:49 Qiao Zixin

The main idea of the topic :

Given a single linked list , It is required to decompose into two linked lists , The first one is to remove the list of nodes with repeated values of absolute values , The second is a list of removed nodes

Algorithm ideas :

use first node The node that stores all input ,removed Store nodes that need to be deleted . Because of the need to judge node Whether nodes in need to be deleted , We use isExist Indicates whether a node with the same absolute value as the node data exists , Use work_n Save the current point in node Which node of , For the initial begin_address, as long as isExist[abs(node[work_n].data)]==true, This indicates that the node needs to be removed to removed In the list , The specific method is to construct a node with the same address and data as the current node temp node , And then add removed in , And use work_r Always save removed The last node address of the linked list , And you need to delete work_n Node to , Use here pre_work_n Save the work_n The address of the precursor node , For the initial -1, Give Way pre_work_n Point to work_n The next node of , also work_n Move back . If isExist[abs(node[work_n].data)]==false, Indicates that the node needs to be retained , take isExist[abs(node[work_n].data)] Set as true, also pre_work_n and work_n All moving back . Finally, output according to the requirements .

Be careful :

1、 Keep the address 5 Significant digits ,-1 Special judgment .
2、 about PAT The list title of the list may exist, the input node is not in the list .

Submit results :

image.png

AC Code :

#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;

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

unordered_map<int,bool> isExist;

int main(){
    int N,begin_address;
    scanf("%d %d",&begin_address,&N);
    Node p{};
    for (int i = 0; i < N; ++i) {
        scanf("%d %d %d",&p.address,&p.data,&p.next);
        node[p.address] = p;
    }
    int work_n = begin_address;// work_n by node The working node of the linked list 
    int pre_work_n = -1;//pre_work_n by work_n stay node The forerunner of 
    //  structure removed Head node of 
    Node head{100004,-1,-1};
    removed[head.address] = head;
    int work_r = head.address;//work_r by removed The working node of the linked list 
    while (work_n!=-1){
        int data = abs(node[work_n].data);
        if(isExist[data]){
            //  You need to remove the node 
            Node temp{work_n,node[work_n].data,-1};
            //  By means of tail insertion temp Insert collocation removed In the list 
            removed[temp.address] = temp;
            removed[work_r].next = temp.address;
            work_r = removed[work_r].next;
            //  Delete work_n Point to the node , And update the work_n
            node[pre_work_n].next = node[work_n].next;
            work_n = node[work_n].next;
        } else {
            //  Retain 
            isExist[data] = true;
            pre_work_n = work_n;
            work_n = node[work_n].next;
        }
    }
    //  Output node Linked list 
    for (;begin_address!=-1;begin_address = node[begin_address].next){
        if(node[begin_address].next!=-1){
            printf("%05d %d %05d\n",begin_address,node[begin_address].data,node[begin_address].next);
        } else {
            printf("%05d %d -1\n",begin_address,node[begin_address].data);
        }
    }
    // Output removed Linked list 
    for(int address=removed[100004].next;address!=-1;address=removed[address].next){
        if(removed[address].next!=-1){
            printf("%05d %d %05d\n",address,removed[address].data,removed[address].next);
        } else {
            printf("%05d %d -1\n",address,removed[address].data);
        }
    }
    return 0;
}

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