Delete All Occurrences of a Key in a Doubly Linked List
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 200 - ◆
-1000 ≤ node value ≤ 1000 - ◆
key may appear zero, one, or many times in the list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Filter into a New Array
GoodWalk the list once, copying every value that is NOT equal to the key into a fresh array, then build a brand-new list from that array. Simple and correct, but it allocates an array (and a whole new chain of nodes) the size of the surviving list.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node deleteAllKeyDLL(Node head, int key) {
9 List<Integer> kept = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 if (curr.val != key) {
13 kept.add(curr.val);
14 }
15 curr = curr.next;
16 }
17 Node dummy = new Node(0);
18 Node tail = dummy;
19 for (int v : kept) {
20 tail.next = new Node(v);
21 tail = tail.next;
22 }
23 return dummy.next;
24 }
25}Optimal — Bypass Matching Nodes In Place
OptimalNo copy is needed. Keep a running pointer at the last kept node (initially a dummy node in front of head). Walk the real list: for each node, if its value matches the key, simply skip it by pointing the last-kept node's next straight past it — the matching node is never linked into the answer. Otherwise, advance the last-kept pointer to this node. One pass, no extra memory. In a true doubly linked list, the node right after a deleted one would also get its .prev pointed back to the last kept node.
O(n)O(1) extra1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node deleteAllKeyDLL(Node head, int key) {
9 Node dummy = new Node(0);
10 dummy.next = head;
11 Node lastKept = dummy;
12 Node curr = head;
13 while (curr != null) {
14 if (curr.val == key) {
15 lastKept.next = curr.next;
16 } else {
17 lastKept = curr;
18 }
19 curr = curr.next;
20 }
21 return dummy.next;
22 }
23}