关于算法-数据结构:PAT甲级1097-Deduplication-on-a-Linked-List

题目粗心:

给定一条单链表, 要求合成为两条链表, 第一条是去除绝对值反复数值结点的链表, 第二条是去除的结点组成的链表

算法思路：

首先应用 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;
}