Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Linked List

Delete All Occurrences of a Key

Easy · Linked List · Asked at Amazon, Microsoft, TCS, Infosys, Wipro

Delete every node whose value equals key and print the remaining list. If the list becomes empty, print EMPTY.

Input

First line: n key. Second line: the n node values.

Output

The remaining list, or EMPTY.

Constraints

The head itself may need deleting (several times). A dummy node in front of the head keeps the code simple.

Example 1

Input

7 6
1 2 6 3 4 5 6

Output

1 2 3 4 5

Example 2

Input

4 7
7 7 7 7

Output

EMPTY

Hints

  1. Several nodes at the start may need deleting, so put a dummy node before the head.
  2. From the dummy, look one node ahead: if it holds the key, unlink it; otherwise step forward.

Approach

With prev = dummy, check prev.next. If its value is the key, bypass it (prev.next = prev.next.next) without moving prev; else move prev forward. At the end dummy.next is the new head; if it is null, print EMPTY.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *next = nullptr;
    Node(long long v) : val(v) {}
};

int main() {
    int n;
    long long key;
    cin >> n >> key;
    Node dummy(0), *t = &dummy;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        t = t->next = new Node(x);
    }
    for (Node *prev = &dummy; prev->next;) {
        if (prev->next->val == key) prev->next = prev->next->next;
        else prev = prev->next;
    }
    if (!dummy.next) cout << "EMPTY\n";
    for (Node *p = dummy.next; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
    return 0;
}

Python solution

import sys


class Node:
    def __init__(self, val):
        self.val, self.next = val, None


data = list(map(int, sys.stdin.read().split()))
n, key = data[0], data[1]
dummy = tail = Node(0)
for v in data[2 : 2 + n]:
    tail.next = Node(v)
    tail = tail.next
prev = dummy
while prev.next:
    if prev.next.val == key:
        prev.next = prev.next.next
    else:
        prev = prev.next
out, p = [], dummy.next
while p:
    out.append(p.val)
    p = p.next
print(*out if out else ["EMPTY"])

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node next;
        Node(long v) { val = v; }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long key = sc.nextLong();
        Node dummy = new Node(0), t = dummy;
        for (int i = 0; i < n; i++) t = t.next = new Node(sc.nextLong());
        Node prev = dummy;
        while (prev.next != null) {
            if (prev.next.val == key) prev.next = prev.next.next;
            else prev = prev.next;
        }
        if (dummy.next == null) {
            System.out.println("EMPTY");
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (Node p = dummy.next; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
        System.out.println(sb);
    }
}

Solve Delete All Occurrences of a Key online · All practice problems