pointersP0201

Detaching train cars with a pointer to a pointer

There is a train of numbered cars linked in a line.
At first it has no cars. There are five commands. - front x: attach a new car numbered x at the front. - back x: attach a new car numbered x at the back. - cut x: detach the first car numbered x, looking from the front.
If there is no such car, do nothing. - rev: reverse the order of the whole train. - show: print on one line the current number of cars k followed by the k car numbers from the front, separated by single spaces.
If there are no cars, print just 0. The first line gives the number of commands q, and the next q lines give one command each. Try solving it with a linked list where each car holds its number and a pointer to the next car. Carry the train as a pointer head to the first car and a pointer to a pointer tailp that points to the last car's next slot. Write cut without treating the first car specially: make it a function that walks by moving Node **pp, the address of "the pointer that points to the current car".

Input: 1 ≤ q ≤ 10,000, 1 ≤ x ≤ 9,999.
All show commands together print at most 30,000 car numbers.
show appears at least once.
Output: One line per show

Example 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 Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 2 languages

This problem accepts only C and C++.
Only those two have Node **, which stores the address of a pointer variable in another pointer.
Python, JavaScript, TypeScript, Java and Craykon can point to the next car with a reference, but cannot hold the address of 'the slot that holds the reference', so to detach the first car they change head separately or use a dummy first car.
C# uses pointers only inside unsafe, and imitates this with ref locals (re-pointed with pp = ref pp.Next since C# 7.3).
In C and C++, walking with for (Node **pp = &t->head; *pp; pp = &(*pp)->next) makes *pp the head itself at the first car and the previous car's next itself in the middle, so the single line *pp = gone->next; detaches a car anywhere.
Keeping the place to attach at the back in Node **tailp (&head when empty) with the same idea gives *tailp = nd; tailp = &nd->next;.
Functions that change the train take its address, as in Train *t.
The C++ solution keeps the cars in a std::deque<Node>: a std::vector moves its elements when it grows, so Node * pointers you already hold would point to the wrong place.
Four traps: ① In C, taking it by value as in void cut(Train t, int x) still detaches middle cars correctly (the cars are linked by pointers), but detaching the first car leaves the real head unchanged, and detaching the last car leaves the real tailp unchanged.
② If you detach the last car and do not fix it with tailp = pp, the next back attaches behind the car you already detached and vanishes.
③ The common approach of walking with the previous car p and looking at p->next never looks at the first car, so the first car needs special handling; Node **pp does not.
④ If after rev you do not move tailp to the next of the old first car (now the last car), the next back attaches behind the wrong car and cars vanish.

C++main.cpp · 78 lines

#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 lines

#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;}