题解 | #Deduplication on a Linked List (25)#

个人博客的PAT题解

题目

OJ平台

题目详解

就是一个静态链表删除元素的数据结构类型题目，这题最坑的地方在于输出的时候需要地址五位数补0，如果是-1则不用补，导致你明明是对的，还以为是错误的。。🤷‍♂️

• 我用队列存储删除的结点的地址，然后后面再进行连接即可。

解题代码

基本变量

int head, rm_head = -1; //分别用于存储两个链表的头结点地址
int N;

struct node {
    int val;
    int next;

    node() : val(0), next(-1) {}
} linklist[MaxN];

queue<int> St; //存储被删除结点的地址
bitset<MaxN> check(0); //用于查重

Input函数

//输入和构建链表
void Input() {
    scanf("%d%d", &head, &N);
    int c = N;
    while (c--) {
        int addr, val, next;
        scanf("%d%d%d", &addr, &val, &next);
        linklist[addr].val = val;
        linklist[addr].next = next;
    }
}

handle函数

//处理链表的去重问题
void handle() {
    //正常删除链表结点的处理方式
    int pre = head;
    check[abs(linklist[head].val)] = 1;
    for (int i = linklist[pre].next; i != -1; i = linklist[i].next) {
        int val = abs(linklist[i].val);
        if (!check[val]) {
            check[val] = 1;
            pre = i;
        }//一旦出现重复结点，把这个结点删除就行，删除结点的操作需要双指针辅助
        else {
            linklist[pre].next = linklist[i].next;
            St.push(i);
        }
    }
    if (St.empty())
        return;
    //根据队列进行正确连接
    int num = St.front();
    St.pop();
    rm_head = num;
    while (!St.empty()) {
        linklist[num].next = St.front();
        num = linklist[num].next;
        St.pop();
    }
    linklist[num].next = -1;
}

print函数

//打印链表即可---注意小坑--(地址打印五位数字，少了补0,-1时不能打印五位数)
void print() {
    handle();
    for (int i = head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
    if (rm_head == -1)
        return;
    printf("\n");
    for (int i = rm_head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
}

整合代码提交

效率还行

#include<bits/stdc++.h>
#define MaxN 100000
using namespace std;
int head, rm_head = -1; //分别用于存储两个链表的头结点地址
int N;

struct node {
    int val;
    int next;

    node() : val(0), next(-1) {}
} linklist[MaxN];

queue<int> St; //存储被删除结点的地址
bitset<MaxN> check(0); //用于查重

//输入和构建链表
void Input() {
    scanf("%d%d", &head, &N);
    int c = N;
    while (c--) {
        int addr, val, next;
        scanf("%d%d%d", &addr, &val, &next);
        linklist[addr].val = val;
        linklist[addr].next = next;
    }
}

//处理链表的去重问题
void handle() {
    //正常删除链表结点的处理方式
    int pre = head;
    check[abs(linklist[head].val)] = 1;
    for (int i = linklist[pre].next; i != -1; i = linklist[i].next) {
        int val = abs(linklist[i].val);
        if (!check[val]) {
            check[val] = 1;
            pre = i;
        }//一旦出现重复结点，把这个结点删除就行，删除结点的操作需要双指针辅助
        else {
            linklist[pre].next = linklist[i].next;
            St.push(i);
        }
    }
    if (St.empty())
        return;
    //根据队列进行正确连接
    int num = St.front();
    St.pop();
    rm_head = num;
    while (!St.empty()) {
        linklist[num].next = St.front();
        num = linklist[num].next;
        St.pop();
    }
    linklist[num].next = -1;
}

//打印链表即可---注意小坑--(地址打印五位数字，少了补0,-1时不能打印五位数)
void print() {
    handle();
    for (int i = head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
    if (rm_head == -1)
        return;
    printf("\n");
    for (int i = rm_head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
}

int main() {
    Input();
    print();
    return 0;
}