Time: April 15, 2021
Topic source: Group programming ladder competition - practice set

Title Description:

Given a linked list L with integer key values, you need to delete the key value nodes with duplicate absolute values. That is, for each key value K, only the node with the first absolute value equal to K is reserved. At the same time, all deleted nodes must be saved in another linked list. For example, given that l is 21 → - 15 → - 15 → - 7 → 15, you need to output the duplicate linked list 21 → - 15 → - 7 and the deleted linked list - 15 → 15.

Input format:

Enter the address of the first node of L given in the first line and a positive integer N (≤ 105, the total number of nodes). The address of a node is a non negative 5-bit integer, and the NULL address is represented by − 1.

Then N lines, each describing 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 integer with an absolute value of no more than 10 4, and the next node is the address of the next node.

Output format:

First output the linked list after de duplication, and then output the deleted linked list. Each node occupies one line and is output according to the input format.

Sample input:

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

Output example:

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

C language solution:

1. Array solution

The best way to solve the problem is not to treat the problem as a problem, so the best way to solve the linked list is not to treat the linked list as a linked list, unless you can use the linked list.

Define an Abs [] array. If the absolute value 15 exists, Abs[15] = 1, otherwise it is 0;

The number of node 00100 is saved in Number[00100], and the next node of node 00100 is saved in Next[00100].

Check nodes one by one. If Abs[next] = 1 corresponding to the number of nodes, put this node into the sub linked list and delete it from the main linked list; If Abs[next] = 0, change it to 1 and connect the node with the previous node.

Finally, seal the two linked lists and output them.
Note that if there are no deleted nodes, the sub linked list (the third test point) will not be output.
Note the address format of the output.

#include<stdio.h>
#include<math.h>
int main(){

	int Number[100000] = {}, Next[100000] = {}, Abs[100000] = {};
	int index, n, i, head, node = -1, next, fhead = -1, fnode;
	
	scanf("%d%d", &head, &n);
	for(i=0; i<n; i++){
		scanf("%d", &index);
		scanf("%d", &Number[index]);
		scanf("%d", &Next[index]);
	}
	
	next = head;
	while(next != -1){
		if(Abs[abs(Number[next])] == 1){
			// next needs to be deleted and transferred to the sub linked list 
			if(fhead == -1){
				fhead = next;
				fnode = next;
				next = Next[next];
				continue;
			}
			Next[fnode] = next;
			fnode = next;
			// Delete the next node from the main chain list 
			Next[node] = Next[next];
		}else{
			// Node retention, recorded to Abs [] 
			if(node == -1){
				Abs[abs(Number[next])] = 1;
				node = next;
				next = Next[next];
				continue;
			}
			Next[node] = next;
			Abs[abs(Number[next])] = 1;
			node = next;
		}
		next = Next[next];
		
	}
	Next[fnode] = -1;
	Next[node] = -1;
	
	// Output master list 
	node = head;
	while(Next[node] != -1){
		printf("%05d %d %05d\n", node, Number[node], Next[node]);
		node = Next[node];
	}
	printf("%05d %d %d\n", node, Number[node], Next[node]);
	
	// Output sub linked list 
	if(fhead == -1){	// Third test point
		return  0; 
	}
	fnode = fhead;
	while(Next[fnode] != -1){
		printf("%05d %d %05d\n", fnode, Number[fnode], Next[fnode]);
		fnode = Next[fnode];
	}
	printf("%05d %d %d\n", fnode, Number[fnode], Next[fnode]);
	
	return 0;
}