题目地址：https://pintia.cn/problem-sets/994805046380707840/problems/994805072641245184

题目

解题思路：

我的：先遍历一遍链表确定哪些结点需要删掉（标记数组），把结点对应的地址和值存入相应的结构体数组中,再遍历整个链表，确定完整的保留链表和删除链表

看了别人的代码恍然大悟：因为已经存好了两个数组，那么除最后一个外，下一个结点的地址是上一个结点的next地址值。。。傻掉了。。这样这个题就真的是很简单了(´･Д･)」

大概花了40多分钟想和写，代码也写的比较长，不够精简，感觉数据结构的东西应用的很不熟。。多练吧！！

天梯的东西一直做的很差。。平时闲的时候尽量把pat上的题做做吧。

 

ac代码： 

自己原本的代码：（跳过吧） 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 100005
typedef long long ll;
const ll inf=1e+18;
using namespace std;
struct Node{
    int add,val,nex;
}rem[maxn],del[maxn];
int fadd,n,num1=0,num2=0,ne[maxn],d[maxn]={0},value[maxn],vis[maxn]={0};//d[ad]=1说明地址为ad的结点要被删除
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d",&fadd,&n);
    int a,b,c,ad,p;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        value[a]=b;ne[a]=c;
    }
    ad=fadd;
    while(ad!=-1)
    {
        if(!vis[abs(value[ad])])
        {
            d[ad]=0;
            vis[abs(value[ad])]=1;
            rem[++num1].val=value[ad];
            rem[num1].add=ad;
        }
        else
        {
            d[ad]=1;//结点删除的标志
            del[++num2].val=value[ad];
            del[num2].add=ad;
        }
        ad=ne[ad];
    }
    if(num1>=1) //至少有1个保留的结点
    {
        int nn = 1;
        ad = rem[nn].add;
        p = ne[ad];
        while (1)
        {
            if (p == -1)
            {
                rem[nn].nex = -1;
                break;
            } else if (!d[p])
            {
                rem[nn++].nex = p;
                ad = p;
                p = ne[ad];
            } else//当前结点被删除
                p = ne[p];
        }
        for(int i=1;i<=num1;i++)
        {
            printf("%05d %d ",rem[i].add,rem[i].val);
            if(rem[i].nex==-1)
                printf("-1\n");
            else
                printf("%05d\n",rem[i].nex);
        }
    }
    if(num2>=1)
    {
        int mm = 1;
        ad=del[1].add;
        p=ne[ad];
        while (1)
        {
            if (p == -1)
            {
                del[mm].nex = -1;
                break;
            } else if (d[p])
            {
                del[mm++].nex = p;
                ad = p;
                p = ne[ad];
            }
            else//当前结点未被删除
                p = ne[p];
        }
        for(int i=1;i<=num2;i++)
        {
            printf("%05d %d ",del[i].add,del[i].val);
            if(del[i].nex==-1)
                printf("-1\n");
            else
                printf("%05d\n",del[i].nex);
        }
    }
    return 0;
}

改进的代码：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 100005
typedef long long ll;
const ll inf=1e+18;
using namespace std;
struct Node{
    int add,val;
}rem[maxn],del[maxn];
int fadd,n,num1=0,num2=0,ne[maxn],d[maxn]={0},value[maxn],vis[maxn]={0};//d[ad]=1说明地址为ad的结点要被删除
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d",&fadd,&n);
    int a,b,c,ad,p;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        value[a]=b;ne[a]=c;
    }
    ad=fadd;
    while(ad!=-1)
    {
        if(!vis[abs(value[ad])])
        {
            d[ad]=0;
            vis[abs(value[ad])]=1;
            rem[++num1].val=value[ad];
            rem[num1].add=ad;
        }
        else
        {
            d[ad]=1;//结点删除的标志
            del[++num2].val=value[ad];
            del[num2].add=ad;
        }
        ad=ne[ad];
    }
    for(int i=1;i<=num1;i++)
    {
        printf("%05d %d ",rem[i].add,rem[i].val);
        if(i==num1)
            printf("-1\n");
        else
            printf("%05d\n",rem[i+1].add);
    }
    for(int i=1;i<=num2;i++)
    {
        printf("%05d %d ",del[i].add,del[i].val);
        if(i==num2)
            printf("-1\n");
        else
            printf("%05d\n",del[i+1].add);
    }
    return 0;
}