Challenge: Remove a Value Everywhere

Lab C++ Intermediate 20 points

Build a linked list, then remove every node with the target value (including at the head), freeing each removed node with delete. Print what's left, or empty.

Input

Line 1: n. Line 2: n whole numbers. Line 3: the target.

Output

The remaining values, or empty.

Example

Input

5
7 1 7 2 7
7

Output

1 2

Sample input available Sample output available

Editor

C++

Hints

Put a dummy node in front of the head.

If prev->next holds the target, skip it and delete it; otherwise move prev on.

Solution explanation

The dummy node removes the special case for the head.

Show solution

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

int main() {
    int n;
    cin >> n;
    Node* head = nullptr;
    Node* tail = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node(x);
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    int target;
    cin >> target;
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    while (prev->next) {
        if (prev->next->value == target) {
            Node* gone = prev->next;
            prev->next = gone->next;
            delete gone;
        } else {
            prev = prev->next;
        }
    }
    if (!dummy.next) cout << "empty" << endl;
    for (Node* c = dummy.next; c; c = c->next) cout << c->value << (c->next ? " " : "\n");
    return 0;
}

Output

Answer