Delete in a Doubly Linked List

You are given the head of a doubly linked list and an integer x. Delete the node at position x (positions are 1-indexed, so the first node is position 1) and return the head of the updated list.

Each node stores an integer in val and holds two pointers: next (to the node after it) and prev (to the node before it). When you remove a node from the middle, its two neighbours must be stitched back together in both directions. When you remove the first node, the new head's prev must become null.

The list is serialized as space-separated values from head to tail. If deleting the only node leaves the list empty, return the empty list.

Hints

· Stuck? Reveal one nudge at a time.

You do not need to move any values — deleting a node is about repointing links.

In a doubly linked list the node in front of you already knows who is behind it via prev, so you never need a trailing pointer.

Handle x == 1 on its own: promote head.next to the new head and clear its prev; every other position is the same two-line stitch.

Common doubts

Deleting position 1 has no left neighbour to rewire. Instead you promote head.next to the new head and set its prev to null.

Its next is null, so only the left stitch runs: node.prev.next = null. Guard the node.next.prev write so you do not dereference null.

Yes. Leaving a stale prev means the head still points backward at a deleted node, which quietly breaks any reverse traversal.

Interview follow-ups

· What an interviewer asks next.

Search for the first node whose val matches, then apply the same prev/next splice — the removal logic is identical once you have the node.

An LRU cache pairs a hash map with a doubly linked list; O(1) deletion via this exact splice is what lets it evict and re-insert nodes in constant time.

Fun facts

The four-pointer splice you learn here is the beating heart of every LRU cache — the map finds the node, the list deletes it in O(1).
Browser back/forward history, text-editor undo stacks, and music playlists are all doubly linked lists using this same delete-and-relink move.

Asked at

AmazonMicrosoftAdobeGoogle

Frequently Sometimes Occasionally

Example 1

Input: list = 1 <-> 3 <-> 2, x = 3
Output: 1 <-> 3
Position 3 holds the value 2. Removing it leaves 1 <-> 3.

Example 2

Input: list = 1 <-> 5 <-> 2 <-> 9, x = 1
Output: 5 <-> 2 <-> 9
Position 1 is the head (value 1). Removing it makes 5 the new head, with its prev set to null.

Constraints

- 1 <= x <= size of the linked list <= 10^6 - 0 <= node.val <= 10^4

Deleting a node from a doubly linked list is a rite of passage: it teaches you to think about pointers flowing in two directions at once. Get the four pointer moves right and this pattern never scares you again.

Prerequisites

Before you start

· Concepts used directly in the solution.

Doubly linked list. Each node carries val plus two pointers, next and prev, so you can walk the list forwards and backwards.

Pointer rewiring. Deleting a node means re-linking its neighbours to each other, not shifting data.

Head vs middle case. Removing the first node has no left neighbour, so it needs its own branch.

Understand the problem

Restated plainly: walk to the node sitting at position x, unhook it, and let its prev and next neighbours point at each other. Return whatever the head is afterwards (it changes only when x == 1).

Worked example — list = 1 <-> 3 <-> 2, x = 3

positions:  1     2     3
           [1] <-> [3] <-> [2]
                          ^ delete this

[3].next was [2]  ->  set [3].next = null
[2].prev was [3]  ->  node is unhooked

result:    [1] <-> [3]

Clarifying questions

Asking about the shape of the input before writing a single line is what separates a senior candidate from someone who codes into a corner.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is x always a valid position between 1 and the list length?”

If x could exceed the size, I would need a bounds check before dereferencing a null pointer.

Edge cases

“Can the list have a single node that then becomes empty?”

Deleting position 1 of a one-node list must return an empty list, not a dangling node.

“When I delete the head, must the new head have prev set to null?”

Yes — a stale prev pointer is a silent bug that breaks any backward traversal later.

Constraints & scale

“How large can the list get?”

Up to a million nodes, so a single O(n) pass is expected and O(1) extra space is preferred.

The ideal opening — say it like this

Before I start, I have a few clarifying questions.

First — can I assume x is always between 1 and the length of the list?

And finally — when I delete the head, you want the new head's prev pointer cleared to null, correct?

Key observations

1Aha

Deletion is local — only two neighbours change

Once you stand on the target node, the entire rest of the list is irrelevant. The only pointers that move belong to the node's immediate prev and next. That is why the actual removal is O(1) once you have found the node.

2Aha

A doubly linked list hands you the left neighbour for free

In a singly linked list you must track the previous node yourself. Here, node.prev already points to it — so you never need a trailing pointer. This is the whole payoff of the extra pointer.

singly:  need a lagging 'prev' variable
doubly:  node.prev is already there

3Aha

The head is the only special case

Deleting position x == 1 has no left neighbour to rewire. Handle it first: promote head.next to the new head and null out its prev. Every other position follows the same two-line stitch.

Brute force vs optimal

	Rebuild copy	In-place splice
Time	O(n)	O(n)
Space	O(n)	O(1)
Idea	copy every node except x	rewire prev/next around x

Both walk the list once, but the optimal approach touches only a handful of pointers and allocates nothing. Full code for each is in the Approaches selector below.

Summary

Key takeaway

To delete from a doubly linked list: find the node, then let its neighbours join hands — prev.next = node.next and node.next.prev = node.prev — treating the head as the one special case.

if x == 1: head = head.next; if head: head.prev = null; return head
walk to the node at position x
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
return head