526互联

团体天梯练习 L2-002 链表去重

发布时间 2023-04-17 00:50:30作者: Amαdeus

L2-002 链表去重

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

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤ $ 10^{5} $ ，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 −1 来表示。

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过 $ 10^{4} $ 的整数，下一个结点是下个结点的地址。

输出格式：

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

输入样例：

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

解题思路

这道题是典型的数据结构题，只要对用数组实现静态链表比较熟悉，就很好做啦。主要是要保持链表的前后地址一致，对于去重的方法，用一个vis数组记录abs(x)是否被访问过即可。不过题目中存在一些坑，比如有可能存在删除链表为空的情况，此时删除链表是不需要输出任何东西的。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

static const int N = 1e5 + 10;
int head, e[N], ne[N], n;   //链表头节点 链表值域 链表指针域 链表长度
bool vis[N];       //记录键值的绝对值是否被访问过
struct node{
    int idx, val, nex;
};
vector<node> res, del;

void show(vector<node> &v){
    int n = (int)v.size();
    node p;
    for(int i = 0; i < n - 1; i ++ ){
        p = v[i];
        p.nex = v[i + 1].idx;   //前后地址要保持一致
        printf("%05d %d %05d\n", p.idx, p.val, p.nex);
    }
    if(!v.empty()){
        p = v.back();
        printf("%05d %d %d\n", p.idx, p.val, -1);
    }
}

int main(){
    scanf("%d%d", &head, &n);
    for(int i = 1; i <= n; i ++ ){   //初始链表
        int idx, val, nex; scanf("%d%d%d", &idx, &val, &nex);
        e[idx] = val, ne[idx] = nex;
    }

    for(int i = head; ~i; i = ne[i]){
        int x = e[i];
        node p = {i, x, ne[i]};
        if(!vis[abs(x)]) res.push_back(p), vis[abs(x)] = true;  //如果没有被访问过 加入答案序列
        else del.push_back(p);   //否则加入删除序列
    }

    show(res);   //输出去重链表
    show(del);   //输出删除链表

    return 0;
}