Remove every copy of a value

Read n numbers into a linked list, in order, and a number x. Remove every node whose value is x, freeing each removed node. Then print what is left, or empty if nothing is left.

What to build

A function that removes every node holding a given value from a linked list.

Requirements

Remove matching nodes at the head first.
For later nodes, link the node before to the node after, then free the removed node.
Print empty when nothing is left.

Input

The first line has n (1 ≤ n ≤ 1000). The second line has the n numbers. The third line has x.

Output

The numbers left in the list, in order, separated by spaces; or empty.

Constraints

1 ≤ n ≤ 1000.

Example

Input:

6
1 2 3 2 4 2
2

Output:

1 3 4

Why it works

After a removal the next node has not been checked yet, so the walk moves forward only when nothing was removed. That is how copies next to each other are all caught.

Examples

Example 1 · Input

6
1 2 3 2 4 2
2

Expected output

1 3 4

Example 2 · Input

3
7 7 7
7

Expected output

empty

Hints

Hint 1

First remove matching nodes at the head, moving head each time.

Hint 2

Then walk with p and look one node ahead: if p->next holds x, link p to the node after it and free the removed one.

Hint 3

Only move p forward when you did not remove a node.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
} Node;

Node *remove_all(Node *head, int x) {
    while (head != NULL && head->value == x) {
        Node *next = head->next;
        free(head);
        head = next;
    }
    Node *p = head;
    while (p != NULL && p->next != NULL) {
        if (p->next->value == x) {
            Node *gone = p->next;
            p->next = gone->next;
            free(gone);
        } else {
            p = p->next;
        }
    }
    return head;
}

int main(void) {
    int n, x;
    scanf("%d", &n);
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *p = malloc(sizeof(Node));
        scanf("%d", &p->value);
        p->next = NULL;
        if (head == NULL) head = p;
        else tail->next = p;
        tail = p;
    }
    scanf("%d", &x);
    head = remove_all(head, x);
    if (head == NULL) printf("empty");
    for (Node *p = head; p != NULL; p = p->next) {
        if (p != head) printf(" ");
        printf("%d", p->value);
    }
    printf("\n");
    return 0;
}

Lesson: Singly linked lists →