L2-002 链表去重

L2-002 链表去重 (25 分)

如果没有要删除的结点，就不输出任何数据

部分测试点

测试点2

00001 3
00001 1 00002
00002 2 -1
00003 3 00004

00001 1 00002
00002 2 -1

测试点3

00100 1
00100 2 -1

00100 2 -1

解题思路

用结构体存储链表，然后遍历一遍链表，遍历过程中数据没有被删除的加入一个结构体数组中，并用变量记录数目，被删除的数据加入另一个结构体数组中，最后分别遍历输出即可。

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

bool st[N];

struct node
{
    int add;
    int num;
    int ne;
    node(){};
    node(int a, int b) { add = a, num = b; }
} a[N], b[N], c[N];

int main()
{
    int sta;
    cin >> sta;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        cin >> a[t].num >> a[t].ne;
    }
    int t = sta;
    int cnt = 0; // 删除的结点个数
    int res = 0; // 原链表剩余结点个数
    // 遍历链表判断
    for (int i = 1; t != -1; i++)
    {
        if (st[abs(a[t].num)])
        {
            c[++cnt] = {t, a[t].num};
        }
        else
        {
            b[++res] = {t, a[t].num};
            st[abs(a[t].num)] = true;
        }
        t = a[t].ne;
    }
    // 输出结果
    for (int i = 1; i < res; i++)
    {
        printf("%05d %d %05d\n", b[i].add, b[i].num, b[i + 1].add);
    }
    printf("%05d %d -1\n", b[res].add, b[res].num);
    for (int i = 1; i < cnt; i++)
    {
        printf("%05d %d %05d\n", c[i].add, c[i].num, c[i + 1].add);
    }
    if (cnt)
        printf("%05d %d -1\n", c[cnt].add, c[cnt].num);
    return 0;
}