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
- 1 ≤ n ≤ 10^5
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
- Several nodes at the start may need deleting, so put a dummy node before the head.
- 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