PTA ladder game exercise set l2-002 linked list de duplication

The chain watch is weightless

Given a linked list with integer keys L, You need to delete the key node where the absolute value is repeated . For each key value K, Only the first absolute value is equal to K The nodes of are reserved . meanwhile , All deleted nodes must be saved in another linked list . For example, given L by 21→-15→-15→-7→15, You need to output the list after de duplication 21→-15→-7, And the deleted list -15→15.

Input format ：
Enter... On the first line L The address of the first node and a positive integer N（≤10⁵, Is the total number of nodes ）. The address of a node is nonnegative 5 An integer , Empty address NULL use -1 To express .

And then N That's ok , Each line describes a node in the following format ：

 Address   Key value   Next node 

Where the address is the address of the node , The key value is an absolute value that does not exceed 10⁴ The integer of , The next node is the address of the next node .

Output format ：
First output the list after de duplication , Then output the deleted list . Each node occupies a row , Output... In input format .

sample input ：

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

sample output ：

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

General idea ： Use structure as linked list node , Save the current node address , value , And the address of the next node . Simulate the mapping relationship between the address and the linked list node of the container with the key value . Address as key , The linked list node uses the key to find the value for the value . In a map1 The mapping relationship between the stored address and the linked list node . With another map2 The current value of the tag has not appeared . The value of the linked list node is the key , The value is true perhaps false, If the current key, that is, the current linked list node value, appears, assign the value corresponding to this key to true. The next time this value appears map2 Use this value as a key in to find true. Achieve the goal of de duplication . The value of the new linked list node is saved in the list 1, Then save the existing values into another list 2. You can separate the linked list .
AC Code （C++）

#include <iostream>
#include <map>
#include <vector>
#include <cmath>

using namespace std;

struct listNode
{
    
	string idAddress;			//  Current node address 
	int variable;				//  value 
	string nextIdAddress;		//  Next node address 
};

map<string, listNode> isList;				//  Used to manage linked list addresses and linked list nodes 
map<unsigned int, bool> auditListNode;		//  Check whether there are duplicates in the marked linked list nodes 

int main()
{
    
	string head;
	cin >> head;			//  Chain head 
	int n;
	cin >> n;				//  The number of linked list nodes is the length of the linked list 
	
	for (int i = 0; i < n; i++)
	{
    
		string thisNowIdAddress;		//  Current node address 
		string nextNowIdAddress;		//  Next node address 
		int value;						//  When the current node value 

		cin >> thisNowIdAddress >> value >> nextNowIdAddress;

		//  The address is associated with the linked list node 
		isList[thisNowIdAddress] = {
     thisNowIdAddress, value, nextNowIdAddress };
	}

	vector<listNode> ansList1;			//  Generated linked list 1
	vector<listNode> ansList2;			//  Generated linked list 2

	for (int i = 0; i < n; i++)
	{
    
		//  Get the current node with the address 
		auto& tempListNode = isList[head];

		//  Judge whether the current value has appeared 
		if (!auditListNode[abs(tempListNode.variable)])
		{
    
			//  If a new value is found that does not appear, then the tag has appeared 
			auditListNode[abs(tempListNode.variable)] = true;
			//  If the linked list is not empty, there is a previous node 
			//  Then pay the address of the current node to the address of the previous node nextIdAddress
			if (0 != ansList1.size())
				ansList1[ansList1.size() - 1].nextIdAddress = tempListNode.idAddress;
			//  Save the current node into the list 
			ansList1.push_back(tempListNode);
		}
		else
		{
    
			//  If the current value has already appeared, it cannot be put into ansList1 了 
			//  Put the existing value into ansList2
			//  If the linked list is not empty, there is a previous node 
			//  Then pay the address of the current node to the address of the previous node nextIdAddress
			if (0 != ansList2.size())
				ansList2[ansList2.size() - 1].nextIdAddress = tempListNode.idAddress;

			//  Save the current node into the list 
			ansList2.push_back(tempListNode);
		}
		//  The current node is empty, that is nextIdAddress 了   Then the cycle ends and the linked list is gone. The rest is ignored 
		if ("-1" == tempListNode.nextIdAddress)
			break;
		//  The next node address of the current node is paid to head, For the next round head Find the corresponding node from the address in 
		head = tempListNode.nextIdAddress;
	}
	//  The sorted list may be in the end node nextIdAddress Is the wrong address , So it needs to be fixed 
	ansList1[ansList1.size() - 1].nextIdAddress = "-1";
	// ansList2  If there are elements in it, then there is also a linked list , There are also tail nodes nextIdAddress Possibility of error , So also correct 
	if (0 != ansList2.size())
		ansList2[ansList2.size() - 1].nextIdAddress = "-1";
	//  Traverse the output according to the requirements of the topic 
	for (auto& i : ansList1)
		cout << i.idAddress << " " << i.variable << " " << i.nextIdAddress << endl;
	for (auto& i : ansList2)
		cout << i.idAddress << " " << i.variable << " " << i.nextIdAddress << endl;
	return 0;
}

Friends who fail the test can try the following test data .
Test data 1：
Input ：

00001 4
00001 1 00002
00002 1 00003
00003 3 -1
00004 1 00002

Output ：

00001 1 00003
00003 3 -1
00002 1 -1

Test data 2

Input ：

00001 3
00001 1 00002
00002 2 -1
00003 3 00004

Output ：

00001 1 00002
00002 2 -1

Test data 3：

Input ：

00001 3
00003 1 00004
00001 2 00002
00002 1 -1

Output ：

00001 2 00002
00002 1 -1