关于算法-数据结构: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;
}