1075 链表元素分类

1075 链表元素分类

思路：
前面要做的事情是：读取输入，组成原链表

• 每个链表节点用一个结构体表示，结构体内三个参数，分别是当前节点的地址add、值val，以及是否已经被提取为答案链表ext。
  

  
  

• 创建两个结构体数组L和ans，分别代表原链表和新链表
• 创建2个map，对应关系分别是：
  （1）ne:当前地址——下个节点地址
  （2）val:当前地址——值

接下来要做的是从原链表中提取节点组成新链表

• 用三次for循环分别抽取小于0的节点，小于等于K的节点，以及其他节点加入答案链表。
  

  
  

  抽取后的节点的ext值设为-1。
  

  
  

#include
#include
#include

using namespace std;

struct node {
	int add;
	int val;
	int ext;
} L[100005], ans[100005];

map<int, int>ne, val;

int main(void) {
	int add, n, k; cin >> add >> n >> k;
	for (int i = 0; i < n; i++) {
		int a, x, b; cin >> a >> x >> b;
		ne[a] = b;
		val[a] = x;
	}
	int index = 0;
	while (1) {
		L[index].add = add;
		L[index].val = val[add];
		index++;
		add = ne[add];
		if (add == -1) { break; }
	}
	n = index;
	index = 0;
	for (int i = 0; i < n; i++) {  // 提取值小于0的节点
		if (L[i].val < 0) {
			ans[index++] = L[i];
			L[i].ext = -1;
		}
	}
	for (int i = 0; i < n; i++) {  // 提取值小于等于K的节点
		if (L[i].val <= k && L[i].ext != -1) {
			ans[index++] = L[i];
			L[i].ext = -1;
		}
	}
	for (int i = 0; i < n; i++) {  // 提取其他节点
		if (L[i].ext != -1) { ans[index++] = L[i]; }
	}

	for (int i = 0; i < n; i++) {  // 输出答案链表
		if (i + 1 != n) {  // 假如不是最后一个链节点
			printf("%05d %d %05d\n", ans[i].add, ans[i].val, ans[i + 1].add);
		}
		else { // 假如是最后一个链节点(没有L[i+1]了)
			printf("%05d %d -1", ans[i].add, ans[i].val);
		}
	}
	return 0;
}