ポインタP0201

ポインタのポインタで外す列車の車両

番号が書かれた車両を一列につないだ列車がある。
最初は車両が一つもない。
命令は五種類である。
- front x：番号 x の新しい車両を先頭につなぐ。
- back x：番号 x の新しい車両を最後尾につなぐ。
- cut x：前から見て最初に出会う番号 x の車両を一つ外す。
そのような車両がなければ何もしない。
- rev：列車全体の順番を逆にする。
- show：いまの車両の数 k と、前から車両の番号 k 個を、空白一つで区切って一行に出力する。
車両がなければ 0 だけを出力する。
一行目に命令数 q、続く q 行に命令が一つずつ与えられる。
車両ごとに番号と次の車両を指すポインタを持つ連結リストで解いてみよう。
列車は、先頭の車両を指すポインタ head と、最後の車両の next の場所を指すポインタのポインタ tailp で持ち歩く。
cut は先頭の車両を特別扱いせず、「いまの車両を指すポインタ」のアドレス Node **pp を動かしながら歩く関数にしてみよう。

入力: 1 ≤ q ≤ 10,000、1 ≤ x ≤ 9,999。
show が出力する番号は全部合わせて 30,000 個以下。
show は一回以上出てくる。
出力: show ごとに一行

例 1 · stdin

9
back 3
front 1
back 7
cut 3
show
rev
back 2
cut 1
show

stdout

2 1 7
2 7 2

main.py プログラミング言語実行バージョン

入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 2 言語の解答

この問題は C・C++ だけを受け付けます。
ポインタ変数のアドレスをさらにポインタに入れる Node ** はこの二つの言語にしかなく、Python・JavaScript・TypeScript・Java・Craykon は参照で次の車両を指すことはできても「参照が入っている場所」のアドレスは持てないので、先頭の車両を外すときは head を別に変えるか、ダミーの先頭車両を置きます。
C# はポインタを unsafe の中でしか使わず、似たことは ref ローカル変数（C# 7.3 から pp = ref pp.Next で指し直せる）でまねします。
C・C++ では for (Node **pp = &t->head; *pp; pp = &(*pp)->next) で歩くと、*pp は先頭では head そのもの、途中では前の車両の next そのものなので、*pp = gone->next; の一行でどこでも外せます。
最後尾につなぐ場所も同じ考えで Node **tailp（空なら &head）に置けば *tailp = nd; tailp = &nd->next; になります。
列車を変える関数は Train *t のようにアドレスで受けます。
C++ では車両を std::deque<Node> に入れました。
std::vector は大きくなるときに要素を移すので、すでに持っている Node * がおかしな場所を指してしまいます。
落とし穴は四つ：① C で void cut(Train t, int x) のように値で受けると、途中の車両はちゃんと外れますが（車両どうしはポインタでつながっているので）、先頭の車両を外しても本当の head はそのまま、最後の車両を外しても本当の tailp はそのままです。
② 最後の車両を外して tailp = pp で直さないと、次の back がもう外した車両の後ろにつながって消えます。
③ 前の車両 p から p->next を見て歩くよくある方法は、先頭の車両を一度も見ません。
だから先頭だけ別に扱う必要がありますが、Node **pp ならその必要がありません。
④ rev のあと tailp を元の先頭（いまの最後尾）の next に移さないと、次の back が違う車両の後ろにつながって車両が消えます。

C++main.cpp · 78 行

#include <deque>#include <iostream>#include <string> struct Node {    int val;    Node *next = nullptr;}; struct Train {    Node *head = nullptr;    // 첫 칸(비었으면 nullptr)    Node **tailp = &head;    // 마지막 칸의 next 자리(비었으면 &head)     Train() = default;    Train(const Train &) = delete;  // tailp가 자기 멤버를 가리키니 복사하면 안 된다     void push_front(Node *nd) {        nd->next = head;        if (head == nullptr) tailp = &nd->next;        head = nd;    }    void push_back(Node *nd) {        *tailp = nd;        tailp = &nd->next;    }    // pp는 "지금 칸을 가리키는 포인터"의 주소: 첫 칸도 가운데 칸도 *pp만 바꾸면 떼어진다    void cut(int x) {        for (Node **pp = &head; *pp != nullptr; pp = &(*pp)->next) {            if ((*pp)->val == x) {                Node *gone = *pp;                *pp = gone->next;                if (gone->next == nullptr) tailp = pp;                return;            }        }    }    void reverse() {        Node *prev = nullptr, *cur = head;        tailp = cur ? &cur->next : &head;        while (cur != nullptr) {            Node *next = cur->next;            cur->next = prev;            prev = cur;            cur = next;        }        head = prev;    }}; int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    std::deque<Node> pool;  // deque는 뒤에 붙여도 있던 칸의 주소가 바뀌지 않는다(vector는 바뀔 수 있다)    Train t;    int q, x;    std::string cmd;    std::cin >> q;    for (int i = 0; i < q; i++) {        std::cin >> cmd;        if (cmd == "front" || cmd == "back") {            std::cin >> x;            Node *nd = &pool.emplace_back(Node{x});            if (cmd == "front") t.push_front(nd);            else t.push_back(nd);        } else if (cmd == "cut") {            std::cin >> x;            t.cut(x);        } else if (cmd == "rev") {            t.reverse();        } else {            int k = 0;            for (Node *p = t.head; p; p = p->next) k++;            std::cout << k;            for (Node *p = t.head; p; p = p->next) std::cout << ' ' << p->val;            std::cout << '\n';        }    }}

Cmain.c · 93 行

#include <stdio.h>#include <string.h> typedef struct Node {    int val;    struct Node *next;} Node; typedef struct {    Node *head;   /* 첫 칸(비었으면 NULL) */    Node **tailp; /* 마지막 칸의 next 자리(비었으면 &head): 여기에 붙이면 맨 뒤 */} Train; static Node pool[10000]; /* 명령마다 칸은 많아야 하나 생긴다 */static int used = 0; Node *new_node(int val) {    Node *nd = &pool[used++];    nd->val = val;    nd->next = NULL;    return nd;} /* 기차를 바꾸는 함수는 모두 Train의 주소를 받는다 */void push_front(Train *t, Node *nd) {    nd->next = t->head;    if (t->head == NULL) t->tailp = &nd->next;    t->head = nd;} void push_back(Train *t, Node *nd) {    *t->tailp = nd;    t->tailp = &nd->next;} /* pp는 "지금 칸을 가리키는 포인터"의 주소: 첫 칸이든 가운데 칸이든 똑같이 *pp만 바꾸면 떼어진다 */void cut(Train *t, int x) {    for (Node **pp = &t->head; *pp != NULL; pp = &(*pp)->next) {        if ((*pp)->val == x) {            Node *gone = *pp;            *pp = gone->next;            if (gone->next == NULL) t->tailp = pp; /* 마지막 칸을 뗐으면 붙일 자리가 앞으로 온다 */            return;        }    }} void reverse(Train *t) {    Node *prev = NULL, *cur = t->head;    t->tailp = cur ? &cur->next : &t->head; /* 지금 첫 칸이 뒤집은 뒤 마지막 칸 */    while (cur != NULL) {        Node *next = cur->next;        cur->next = prev;        prev = cur;        cur = next;    }    t->head = prev;} void show(const Train *t) {    int k = 0;    for (const Node *p = t->head; p != NULL; p = p->next) k++;    printf("%d", k);    for (const Node *p = t->head; p != NULL; p = p->next) printf(" %d", p->val);    printf("\n");} int main(void) {    int q, x;    char cmd[8];    Train t;    t.head = NULL;    t.tailp = &t.head;    scanf("%d", &q);    for (int i = 0; i < q; i++) {        scanf("%7s", cmd);        if (strcmp(cmd, "front") == 0) {            scanf("%d", &x);            push_front(&t, new_node(x));        } else if (strcmp(cmd, "back") == 0) {            scanf("%d", &x);            push_back(&t, new_node(x));        } else if (strcmp(cmd, "cut") == 0) {            scanf("%d", &x);            cut(&t, x);        } else if (strcmp(cmd, "rev") == 0) {            reverse(&t);        } else {            show(&t);        }    }    return 0;}