NWPU 数据结构 NOJ 005 单链表的删除

题目

已知 $A,B$ 和 $C$ 为三个非递减有序的线性表，均以单链表作为存储结构。现要求对 $A$ 表作如下操作：删去那些既在 $B$ 表中出现又在 $C$ 表中出现的元素。试对单链表编写实现上述操作的算法，并释放 $A$ 表中的无用结点空间。

输入

第一行输入 3 个正整数 $m,n,p\,\,\,(m,n,p\leq 100)$，用空格分开，表示三个线性表中的元素个数，其后 3 行依次输入 $A,B,C$ 表中的元素。

解法

以第一个链表元素为基准，依次把后两个拉到不超过第一个当前枚举的元素的位置，如果三个相等则删除。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

class pNode {
public:
    int x;
    pNode* nxt;
};

int n, m;

void print(pNode* s) {
    pNode *p3 = s;
    while(p3 != NULL) {
        printf("%d ", p3->x);
        p3 = p3->nxt;
    }
    puts("");
}

int n1, n2, n3;

void clean(pNode* s) {
    if(s == NULL) return;
    clean(s->nxt);
    free(s);
}

int main() {
    // freopen("005.in", "r", stdin);
    cin >> n1 >> n2 >> n3;
    pNode* h1 = (pNode*)malloc(sizeof(pNode));
    pNode* r = h1;
    h1->x = -1;
    h1->nxt = NULL;
    while(n1--) {
        int y; cin >> y;
        pNode* o = (pNode*)malloc(sizeof(pNode));
        o->x = y; o->nxt = NULL; r->nxt = o; r = o;
    }
    pNode* h2 = (pNode*)malloc(sizeof(pNode));
    r = h2;
    h2->x = -1;
    h2->nxt = NULL;
    while(n2--) {
        int y; cin >> y;
        pNode* o = (pNode*)malloc(sizeof(pNode));
        o->x = y; o->nxt = NULL; r->nxt = o; r = o;
    }
    pNode* h3 = (pNode*)malloc(sizeof(pNode));
    r = h3;
    h3->x = -1;
    h3->nxt = NULL;
    while(n3--) {
        int y; cin >> y;
        pNode* o = (pNode*)malloc(sizeof(pNode));
        o->x = y; o->nxt = NULL; r->nxt = o; r = o;
    }
    pNode *p1, *p2, *p3;
    p1 = h1->nxt;
    p2 = h2;
    p3 = h3;
    pNode* pp1 = h1;
    while(p1 != NULL) {
        int ref = p1->x;
        while(p2->nxt != NULL && p2->nxt->x <= ref) {
            p2 = p2->nxt;
        }
        while(p3->nxt != NULL && p3->nxt->x <= ref) {
            p3 = p3->nxt;
        }
        if(ref == p2->x && ref == p3->x) {
            pp1->nxt = p1->nxt;
            pNode* dn = p1;
            p1 = p1->nxt;
            free(dn);
        } else {
            pp1 = p1;
            p1 = p1->nxt;
        }
    }
    print(h1->nxt);
    clean(h1);
    clean(h2);
    clean(h3);
    return 0;
}
Code language: PHP (php)