You are given the head of a doubly linked list and an integer key x. Some nodes may hold the value x — one, several, scattered anywhere, or none at all. Delete every node whose value equals x and return the head of the resulting list.
The surviving nodes must keep their original order, and — because this is a doubly linked list — every remaining node's prev and next pointers must be re-stitched so the list is still walkable in both directions. If the old head itself is deleted, the returned head is the first surviving node; if the whole list is deleted, return an empty list.
prev, so instead of patching a left neighbour you advance the head pointer to curr.next. If several leading nodes match, this branch fires repeatedly.curr's actual prev and next, a run of matches unravels one node at a time on its own.curr is unlinked, reading pointers off it is unreliable. Storing nxt = curr.next first guarantees the walk can always advance.prev pointer you track the previous node manually, or use a dummy head so head-deletions need no special case; you set prev.next = curr.next.return turns the same pointer logic into a single-delete.next and prev — is the single reflex behind almost every doubly-linked-list edit.Input: head = 2<->2<->10<->8<->4<->2<->5<->2, x = 2 Output: 10<->8<->4<->5 Every node holding 2 is removed; the four survivors keep their order and stay linked both ways.
Input: head = 9<->1<->3<->4<->5<->1<->8<->4, x = 9 Output: 1<->3<->4<->5<->1<->8<->4 Only the head held 9, so it is unlinked and the second node becomes the new head.
- 1 <= number of nodes <= 10^5 - 0 <= node value <= 10^9 - The list is a valid doubly linked list (every prev/next pair is consistent).
Deleting one known node in a doubly linked list is a two-line pointer dance. Here the twist is all occurrences — the target can sit at the head, at the tail, or bunched together in the middle — and you must handle each spot without ever losing the rest of the list.
prev to the node behind it and next to the node ahead.next and prev sides.prev, so deleting it moves the head pointer forward instead of patching a left neighbour.Plain English: scan the list from head to tail. For each node equal to x, splice it out by wiring its prev and next neighbours together, then continue. Formally, return the head of the list containing exactly the nodes whose value is not x, in their original relative order.
Delete x = 2 from: 2 <-> 2 <-> 10 <-> 8 <-> 4 <-> 2 <-> 5 <-> 2 Head nodes (2,2) drop → head jumps to 10 Middle 2 (between 4 and 5): link 4 <-> 5 Tail 2 drops: 5 becomes the new tail Result: 10 <-> 8 <-> 4 <-> 5
A few sharp questions before coding show you have already spotted the boundary cases an interviewer is waiting to see.
“Can the list be empty to begin with?”
If yes, the loop must simply return an empty head without touching any pointer.
“What if the target appears at the head, the tail, or as a run of consecutive nodes?”
Each needs correct pointer handling — the head has no prev, the tail has no next, and consecutive deletions must not skip a node.
“What if every node equals x?”
The whole list is deleted and we return an empty list, so the head-deletion branch must keep firing.
“How large can the list get?”
Up to 10^5 nodes, so we want a single O(n) pass — no repeated scans.
Before I start, I have a few clarifying questions.
First — can the target sit at the head or tail, and can several matches be adjacent?
And finally — if every node matches, I should return an empty list, correct?
Once you unlink a node, reading its next afterwards is fragile. Save nxt = curr.next before deleting, so the walk always advances safely — even when the current node vanishes.
nxt = curr.next // remember the road ahead ... delete curr ... curr = nxt // step forward regardless
Removing curr is two links: curr.prev.next = curr.next and curr.next.prev = curr.prev. Whichever side is missing (head has no prev, tail has no next) is simply skipped — and when there's no prev, the head pointer itself moves to curr.next.
Because we always splice curr's real neighbours (not assumed ones), a run of consecutive matches unravels correctly node by node — no special case for adjacency is needed.
| Brute force (rebuild) | Optimal (in-place splice) | |
|---|---|---|
| Idea | Collect surviving values, build a fresh list | Unlink matching nodes as you scan |
| Time | O(n) | O(n) |
| Space | O(n) extra | O(1) extra |
Both are linear time, but the optimal version rewires pointers in place and uses no extra memory. The full code for each lives in the Approaches selector below.
Key takeaway
Deleting a node in a doubly linked list is always the same move: join its two neighbours and, if it was the head, advance the head. Save next before you cut, and a single left-to-right pass removes every occurrence in O(n) time and O(1) space.
curr = head
while curr:
nxt = curr.next
if curr.val == x:
if curr.prev: curr.prev.next = curr.next
else: head = curr.next
if curr.next: curr.next.prev = curr.prev
curr = nxt
return head