Topics › Linked List › Medium Problems of DLL

Delete all occurrences of a key in DLL

Hard TUF ID 609 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a doubly linked list and an integer key. Delete every node whose value equals key and return the head of the resulting list. The remaining nodes must keep their relative order, and the list must stay a valid doubly linked list: each node’s prev must point at the node before it and the head’s prev must be null.

Constraints: 0 ≤ n ≤ 10^5, values and key are 32-bit integers. The key may appear at the head, at the tail, several times in a row, or not at all.

Example 1

head = 10 <-> 4 <-> 10 <-> 10 <-> 6 <-> 10, key = 10
answer = 4 <-> 6          // the key was at the head, at the tail and in a run in the middle

Example 2

head = 5 <-> 5 <-> 5, key = 5
answer = (empty list)     // every node matched, so the result is null

Example 3

head = 1 <-> 2 <-> 3, key = 4
answer = 1 <-> 2 <-> 3    // key absent, nothing changes

The problem is rated hard on the sheet not because the idea is deep but because it is easy to leave a dangling prev pointer or lose the head. Both mistakes pass a forward traversal and only show up later, which is what makes them nasty.

Approach 1: Brute force, rebuild the list

Intuition. If pointer surgery feels risky, avoid it. Walk the list, collect every value that is not the key, and build a fresh doubly linked list from those values. The new list is well-formed by construction because we create every link ourselves, in order.

Algorithm.

1. Traverse the list and append each value != key to an ArrayList.
2. For each kept value create a node; link it after the current tail, set its prev to the tail, and make it the new tail. The first node becomes the head.
3. Return the new head (or null if nothing was kept).

static Node bruteForce(Node head, int key) {
    List<Integer> kept = new ArrayList<>();
    for (Node t = head; t != null; t = t.next) {
        if (t.val != key) kept.add(t.val);
    }
    Node newHead = null, tail = null;
    for (int v : kept) {
        Node node = new Node(v);
        if (newHead == null) newHead = node;
        else { tail.next = node; node.prev = tail; }
        tail = node;
    }
    return newHead;
}

Complexity. Time O(n): one pass to collect, one pass to rebuild. Space O(n): the list of values plus a whole new set of nodes.

This is correct and simple, but it defeats the purpose of a linked list. The entire point of the structure is that deletion is a constant-time pointer change once you are standing at the node. Rebuilding also breaks any external references into the list, since every surviving node is a different object from the original.

Approach 2: Optimal, unlink in place

Intuition. In a doubly linked list a node knows both of its neighbours, so deleting it never needs a lookbehind pointer: cur.prev.next = cur.next bypasses it going forward and cur.next.prev = cur.prev bypasses it going backward. The only special cases are the two ends. If cur.prev is null, cur is the head and the head must move to cur.next. If cur.next is null, cur is the tail and there is no prev to fix on the right.

One subtlety: we must save cur.next before cutting the node out, because the method also clears the removed node’s own pointers, and we need to keep walking.

Algorithm.

1. Set cur = head.
2. While cur is not null:
   • Save next = cur.next.
   • If cur.val == key:
     • If cur.prev exists, set cur.prev.next = cur.next; otherwise cur is the head, so set head = cur.next.
     • If cur.next exists, set cur.next.prev = cur.prev.
     • Clear cur.prev and cur.next so the removed node no longer points into the list.
   • Move cur = next.
3. Return head.

static Node optimal(Node head, int key) {
    Node cur = head;
    while (cur != null) {
        Node next = cur.next;                         // save it before any link is cut
        if (cur.val == key) {
            if (cur.prev != null) cur.prev.next = cur.next;
            else head = cur.next;                     // deleting the current head
            if (cur.next != null) cur.next.prev = cur.prev;
            cur.prev = null;
            cur.next = null;
        }
        cur = next;
    }
    return head;
}

Dry run on 10 <-> 4 <-> 10 <-> 10 <-> 6 <-> 10, key 10:

Result: 4 <-> 6. Notice how after deleting the second 10, the third 10 already has prev = 4; the bookkeeping on each deletion is what makes the next deletion correct.

Complexity. Time O(n): each node is visited once and each deletion is O(1). Space O(1): two pointers.

Why does this handle runs of the key correctly? After unlinking cur, the node after it has its prev pointed at the node before cur. So when the loop reaches that next node (via the saved next), its prev is the correct surviving neighbour, and the same two assignments work again. No special “run” handling is needed.

Approach 3: Optimal, with a sentinel in front of the head

Intuition. The if (cur.prev != null) ... else head = ... branch exists only because the head has no predecessor. A classic trick removes the special case entirely: temporarily place a dummy node (a sentinel) in front of the head. Now every real node has a non-null prev, the deletion code is a straight line, and at the end the real head is simply sentinel.next.

Algorithm.

1. Create sentinel, point sentinel.next at head, and set head.prev = sentinel if the list is non-empty.
2. Walk the real nodes exactly as in Approach 2, but always do cur.prev.next = cur.next without a null check.
3. Let newHead = sentinel.next; if it exists, set newHead.prev = null to detach the sentinel.
4. Return newHead.

static Node optimalWithSentinel(Node head, int key) {
    Node sentinel = new Node(0);
    sentinel.next = head;
    if (head != null) head.prev = sentinel;
    Node cur = head;
    while (cur != null) {
        Node next = cur.next;
        if (cur.val == key) {
            cur.prev.next = cur.next;                 // cur.prev is never null thanks to the sentinel
            if (cur.next != null) cur.next.prev = cur.prev;
            cur.prev = null;
            cur.next = null;
        }
        cur = next;
    }
    Node newHead = sentinel.next;
    if (newHead != null) newHead.prev = null;         // detach the sentinel again
    return newHead;
}

Complexity. Time O(n), space O(1); identical to Approach 2 plus one temporary node.

Forgetting step 3 is the classic sentinel bug: the returned head would still have prev pointing at the dummy node, and a backward traversal would walk into it. The test file’s wellFormed check (head’s prev is null, every next.prev points back) is there to catch exactly this.

Edge cases and pitfalls

• Key at the head. The head must move. In Approach 2 this is the else head = cur.next branch; in Approach 3 the sentinel handles it. A method that returns the original head parameter without updating it fails 2 <-> 1, key 2.
• Key at the tail. cur.next is null, so the cur.next.prev assignment must be guarded. Dereferencing it throws a NullPointerException on 1 <-> 2, key 2.
• Every node matches. 5 <-> 5 <-> 5, key 5 must return null. Watch that the loop does not stop early when the head is deleted.
• Empty list. head == null must return null. All three methods handle this with no special code because their loops do not execute.
• Dangling prev. Forgetting cur.next.prev = cur.prev leaves the right neighbour pointing at a deleted node. Forward traversal looks fine; backward traversal, or the next deletion, is wrong.
• Advancing after deletion. Reading cur.next after clearing it would end the loop prematurely. Save next before the surgery.
• Rebuilding versus unlinking. Approach 1 returns new node objects; if anything outside the list holds references to nodes, those references now point into a stale list.

Related problems

• Introduction to Doubly LL covers the node structure and why prev makes deletion O(1).
• Delete head of Doubly Linked List is the single-node version of the head special case.
• Remove duplicates from sorted DLL uses the same unlinking step, choosing which nodes to remove by comparing neighbours.
• Find Pairs with Given Sum in Doubly Linked List is another DLL problem that leans on the prev pointer.