AlgoViz
HomeLinked List

Delete all occurrences of a key in DLL

Hard

Unlink each match, both directions

Problem

Given the head of a doubly linked list and an integer target. Delete all nodes in the linked list with the value target and return the head of the modified linked list.

In simple words

Walk the doubly list, unlinking every node whose value matches the key by fixing its neighbours' pointers.

The idea

Walk the list and, for every node matching the key, connect its prev to its next and its next back to its prev. Because a doubly linked node knows its predecessor, each removal is O(1) with no lookahead needed.

The trick

  • Save the next node before unlinking or the walk stops.
  • Deleting the head means returning a new head; guard for it.
  • One pass, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
1
4
1
0
1
2
3
4
5

Step 1 of 2. Here's the example — head -> 1 <-> 2 <-> 3 <-> 1 <-> 4, target = 1 Values: 1, 2, 3, 1, 4, 1.

1/2
Optimal
timeO(n)spaceO(1)
1cur = head2while cur:3  if cur.val == key:4    if cur.prev: cur.prev.next = cur.next else head = cur.next5    if cur.next: cur.next.prev = cur.prev6  cur = cur.next7return head

Input

array
[1, 2, 3, 1, 4, 1]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3 -> 2 -> 4, key = 2
Output:
1 -> 3 -> 4
Explanation:
Every 2 is removed.

Example 2

Input:
list = 2 -> 2 -> 2, key = 2
Output:
(empty)
Explanation:
All nodes gone → empty.

Example 3

Input:
list = 1 -> 3, key = 2
Output:
1 -> 3
Explanation:
No 2 → unchanged.

Constraints

  • 0 <= number of nodes in the linked list <= 10^5
  • -10^4 <= ListNode.val <= 10^4
  • -10^4 <= target <= 10^4

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.