题目粗心:
给定一条单链表, 要求合成为两条链表, 第一条是去除绝对值反复数值结点的链表, 第二条是去除的结点组成的链表
算法思路：
首先应用 node 存储所有输出的节点，removed 存储须要删除的节点。因为须要判断 node 中的节点是否须要删除，咱们应用 isExist 示意与该节点数据的绝对值雷同的节点是否存在，应用 work_n 保留以后指向在 node 的哪个节点，初始为 begin_address, 只有 isExist[abs(node[work_n].data)]==true，就阐明须要将该节点移除到 removed 链表中，具体方法是结构一个和以后节点地址和数据雷同的 temp 节点，而后增加进 removed 中，并且应用 work_r 始终保留 removed 链表的尾结点地址，并且须要删除 work_n 指向的节点，这里应用 pre_work_n 保留了 work_n 前驱节点地址，初始为 -1，让 pre_work_n 指向 work_n 的下一个节点，并且 work_n 后移即可。如果isExist[abs(node[work_n].data)]==false, 阐明须要保留该节点，将isExist[abs(node[work_n].data)] 置为 true, 并且 pre_work_n 和 work_n 均向后挪动。最初依照要求输入即可。
留神点：
1、地址得保留 5 位有效数字，- 1 得特判。
2、对于 PAT 的链表题目都有可能会存在输出了不在链表上的节点。
提交后果：
AC 代码：
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
struct Node{
int address;
int data;
int next;
}node[100005],removed[100005];
unordered_map<int,bool> isExist;
int main(){
int N,begin_address;
scanf("%d %d",&begin_address,&N);
Node p{};
for (int i = 0; i < N; ++i) {scanf("%d %d %d",&p.address,&p.data,&p.next);
node[p.address] = p;
}
int work_n = begin_address;// work_n 为 node 链表的工作节点
int pre_work_n = -1;//pre_work_n 为 work_n 在 node 中的前驱
// 结构 removed 的头结点
Node head{100004,-1,-1};
removed[head.address] = head;
int work_r = head.address;//work_r 为 removed 链表的工作节点
while (work_n!=-1){int data = abs(node[work_n].data);
if(isExist[data]){
// 须要移除该节点
Node temp{work_n,node[work_n].data,-1};
// 采纳尾插法将 temp 插入搭配 removed 链表中
removed[temp.address] = temp;
removed[work_r].next = temp.address;
work_r = removed[work_r].next;
// 删除 work_n 指向节点，并更新 work_n
node[pre_work_n].next = node[work_n].next;
work_n = node[work_n].next;
} else {
// 保留
isExist[data] = true;
pre_work_n = work_n;
work_n = node[work_n].next;
}
}
// 输入 node 链表
for (;begin_address!=-1;begin_address = node[begin_address].next){if(node[begin_address].next!=-1){printf("%05d %d %05d\n",begin_address,node[begin_address].data,node[begin_address].next);
} else {printf("%05d %d -1\n",begin_address,node[begin_address].data);
}
}
// 输入 removed 链表
for(int address=removed[100004].next;address!=-1;address=removed[address].next){if(removed[address].next!=-1){printf("%05d %d %05d\n",address,removed[address].data,removed[address].next);
} else {printf("%05d %d -1\n",address,removed[address].data);
}
}
return 0;
}