2020-11-10 14:21:49

#### 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 ： #### AC Code ：

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

using namespace std;

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

unordered_map<int,bool> isExist;

int main(){
Node p{};
for (int i = 0; i < N; ++i) {
}
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
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
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;
}
}
} else {
}
}
} else {
}
}
return 0;
}
``````