【PTA】链表去重

绝地灬酷狼 2023-07-01 13:55 4阅读 0赞

#### 题目重述 ####

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 `21→-15→-15→-7→15`，你需要输出去重后的链表 `21→-15→-7`，还有被删除的链表 `-15→15`。

#### 输入格式： ####

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。**一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。**  
随后 N 行，每行按以下格式描述一个结点：

> 地址 键值 下一个结点

其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。

#### 输出格式： ####

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

#### 输入样例： ####

00100 5
    99999 -7 87654
    23854 -15 00000
    87654 15 -1
    00000 -15 99999
    00100 21 23854

#### 输出样例： ####

00100 21 23854
    23854 -15 99999
    99999 -7 -1
    00000 -15 87654
    87654 15 -1

#### 题目思想 ####

如果碰到的值没有被访问过，就标记一下这个值是访问过的，并且提前将这个结点信息存起来。如果碰到的值访问过，就使用另外一个数组存起来。

需要注意的是，这道题，后几个测试点的数据量都比较大，一般没问题，但是存放节点信息用结构体数组就可以，不要用map，我之前不知道为什么觉得map方便，导致最后几个测试点超时，最后换回了结构体数组，才AC。

我真菜啊

#### C++ AC ####

#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    
    struct node
    {
        
        int value;
        int next;
    };
    node nds[100005];
    int v1[100005];//存放删去的
    int v2[100005];//存放未被删去的
    bool isVisit[10005];
    int main()
    {
        
        ios::sync_with_stdio(false);
        int N;
        int  L;
        cin>>L>>N;
        int tmp;
        for(int i=0; i<N; i++)
        {
        
            cin>>tmp;
            cin>>nds[tmp].value>>nds[tmp].next;
    
        }
        int p=L;
        int loc1=0,loc2=0;
        while(true)
        {
        
            if(isVisit[abs(nds[p].value)])//如果之前已经访问过这个值的绝对值
            {
        
                v1[loc1++]=p;//提前存起来
            }
            else
            {
        
                isVisit[abs(nds[p].value)]=true;
                v2[loc2++]=p;//提前存起来
    
            }
            if(nds[p].next==-1)
            {
        
                break;
            }
            p=nds[p].next;
        }
        //将之前提前存起来的结点的下一站进行更新
        for(int i=0; i<loc2; i++)
        {
        
            if(i+1<loc2)
            {
        
                nds[v2[i]].next=v2[i+1];
            }
            else
            {
        
                nds[v2[i]].next=-1;
            }
            //如果下一站是-1，则不需要满足5位补0
            if(nds[v2[i]].next==-1)
            {
        
                printf("%05d %d %d\n",v2[i],nds[v2[i]].value, nds[v2[i]].next);
            }
            else
            {
        
                printf("%05d %d %05d\n",v2[i],nds[v2[i]].value, nds[v2[i]].next);
            }
    
    
        }
        //将之前提前存起来的结点的下一站进行更新
        for(int i=0; i<loc1; i++)
        {
        
            if(i+1<loc1)
            {
        
                nds[v1[i]].next=v1[i+1];
            }
            else
            {
        
                nds[v1[i]].next=-1;
            }
            //如果下一站是-1，则不需要满足5位补0
            if(nds[v1[i]].next==-1)
            {
        
                printf("%05d %d %d\n",v1[i],nds[v1[i]].value, nds[v1[i]].next);
    
            }
            else
            {
        
                  printf("%05d %d %05d\n",v1[i],nds[v1[i]].value, nds[v1[i]].next);
            }
    
        }
        return 0;
    }