2020-11-10 12:44:27

#### The main idea of the topic :

Given N The starting address of nodes is \$begin\$_\$address\$ The single chain table of , Requirements according to data Sort , Then output the linked list

#### Algorithm ideas ：

We use \$node\$ Array stores all the input nodes , Use when typing \$dataToAddress\$ Record data to address mapping ( Data and address are bound , No matter what, it won't change ), For input, there may be nodes that are not on the linked list , So use \$isExist\$ Record all input nodes , In this way, we can judge whether the starting node exists in the input node , The purpose is to solve the problem that the linked list is empty . In the case of only partially valid nodes , We need to traverse \$node\$ Array , And use \$data\$ The array holds the data of all nodes in the linked list ,\$count\$ Record the number of valid nodes , Here the sort is the skill of index sort , Direct pair \$data\$ Array sorting , So reuse \$dataToAddress\$ You can easily know the address of the corresponding node , also \$next\$ It's the next node \$address\$, But be careful , Of the last node \$next\$ by -1, Manual assignment is required , At the same time, you need to record the new starting address as \$data\$ The address of the first node in the array . Finally, output according to the requirements

#### Be careful ：

1、 The input node will be invalid , So we have to traverse the input nodes , Save the information of valid nodes , Test point 1 and 4 Investigate .
2、 Test point 4 Consider the case where all nodes are invalid , It's time to output "0 -1"
3、 Address reservation 5 Significant digits ,-1 Special judgment .

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

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

using namespace std;

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

unordered_map<int,bool > isExist;

int main(){
Node p{};
for (int i = 0; i < N; ++i) {
}
printf("0 -1\n");
return 0;
}
int data[N];//  Save all the data
int count = 0;// The number of nodes in the linked list
}
sort(data,data+count);
for (int i = 0; i < count-1; ++i) {
if(i==0){
//  Record the new starting address
}
}
//  The address of the next node of the last node is -1
} else {
}