摘要
Title: L2-002 链表去重 (25 分)
Tag: 单链表
Memory Limit: 64 MB
Time Limit: 1000 ms

L2-002 链表去重 (25 分)

题意

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

单链表的运用，已知头节点和各个节点的val和next，直接连起来遍历即可
ps: 本身节点的next不一定是最后的next，在最后答案数组中的下一个数才是真正的next

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-04-19 16:37:06
* @FilePath: \ACM\GPLT\L2-002.CPP
* @LastEditTime: 2022-04-20 20:17:37
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

const int N = 1e5 + 10;
int h, e[N], ne[N], st[N];

int n;
signed main()
{
    IOS;
    cin >> h >> n;
    for (int i = 1; i <= n; ++i)
    {
        int address, val, next;
        cin >> address >> val >> next;
        e[address] = val;
        ne[address] = next;
    }

    vector<int> v1, v2;
    for (int i = h; ~i; i = ne[i])
    {
        int val = e[i];
        if (st[abs(val)])
            v2.push_back(i);
        else
        {
            st[abs(val)] = 1;
            v1.push_back(i);
        }
    }
    for (int i = 0; i < SZ(v1); ++i)
    {
        printf("%05lld %lld ", v1[i], e[v1[i]]);
        if (i == SZ(v1) - 1)
            printf("-1\n");
        else
            printf("%05lld\n", v1[i + 1]);
    }
    for (int i = 0; i < SZ(v2); ++i)
    {
        printf("%05lld %lld ", v2[i], e[v2[i]]);
        if (i == SZ(v2) - 1)
            printf("-1\n");
        else
            printf("%05lld\n", v2[i + 1]);
    }
    return 0;
}

L2-002 链表去重 (25 分)

题意

思路

代码