Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Delete all occurrences of a given key in a doubly linked list

HARDProblemSolveExternal Links

Description

You are given the head of a doubly linked list and an integer key. Your task is to delete every node whose value equals the given key and return the head of the modified list.

In a doubly linked list, each node has three components: a data value, a pointer to the next node, and a pointer to the previous node. When you remove a node, you must update the surrounding nodes' pointers so that the list remains properly connected in both directions.

If all nodes in the list contain the key value, the resulting list is empty and you should return null.

Examples

Example 1

Input: DLL: 2 ↔ 2 ↔ 10 ↔ 8 ↔ 4 ↔ 2 ↔ 5 ↔ 2, key = 2

Output: 10 ↔ 8 ↔ 4 ↔ 5

Explanation: The value 2 appears at four positions in the list: the 1st node, 2nd node, 6th node, and 8th node. After removing all four occurrences, the remaining nodes 10, 8, 4, and 5 are reconnected. Node 10 becomes the new head since both original leading nodes held the key value.

Example 2

Input: DLL: 9 ↔ 1 ↔ 3 ↔ 4 ↔ 5 ↔ 1 ↔ 8 ↔ 4, key = 9

Output: 1 ↔ 3 ↔ 4 ↔ 5 ↔ 1 ↔ 8 ↔ 4

Explanation: The value 9 appears only at the head of the list. After removing it, the second node (value 1) becomes the new head. Its prev pointer is updated to null since it is now the first node.

Example 3

Input: DLL: 2 ↔ 2 ↔ 2, key = 2

Output: (empty list)

Explanation: Every node in the list contains the key value 2. After removing all nodes, the list is empty and we return null.

Constraints

  • 1 ≤ Number of nodes ≤ 10^5
  • 0 ≤ Node value ≤ 10^9
  • 0 ≤ key ≤ 10^9
  • Expected Time Complexity: O(n)
  • Expected Auxiliary Space: O(1)

Editorial

Brute Force

Intuition

The simplest way to think about this problem is: walk through every node, collect only the ones that do not match the key, and build a brand new doubly linked list from those collected values.

Imagine you have a line of people holding hands in both directions (a doubly linked list). Some people are wearing red shirts (the key). You want to remove everyone in red. The brute force approach is to ask everyone not wearing red to step aside, then form a brand new line with just those people. You are not rearranging the original line — you are building a completely new one from scratch.

This is straightforward but wasteful: you are creating entirely new nodes rather than reusing the existing ones.

Step-by-Step Explanation

Let us trace through with DLL: 2 ↔ 2 ↔ 10 ↔ 8 ↔ 4 ↔ 2 ↔ 5 ↔ 2, key = 2:

Step 1: Initialize an empty list to collect non-key values.

  • collected = []

Step 2: Visit node with value 2.

  • 2 == key? Yes. Skip this node.
  • collected = []

Step 3: Visit node with value 2.

  • 2 == key? Yes. Skip this node.
  • collected = []

Step 4: Visit node with value 10.

  • 10 == key? No. Add to collected.
  • collected = [10]

Step 5: Visit node with value 8.

  • 8 == key? No. Add to collected.
  • collected = [10, 8]

Step 6: Visit node with value 4.

  • 4 == key? No. Add to collected.
  • collected = [10, 8, 4]

Step 7: Visit node with value 2.

  • 2 == key? Yes. Skip this node.
  • collected = [10, 8, 4]

Step 8: Visit node with value 5.

  • 5 == key? No. Add to collected.
  • collected = [10, 8, 4, 5]

Step 9: Visit node with value 2.

  • 2 == key? Yes. Skip this node.
  • collected = [10, 8, 4, 5]

Step 10: Build a new doubly linked list from collected = [10, 8, 4, 5].

  • Create node 10 (head). Create node 8, link 10 ↔ 8. Create node 4, link 8 ↔ 4. Create node 5, link 4 ↔ 5.

Result: New DLL: 10 ↔ 8 ↔ 4 ↔ 5

Algorithm

  1. Initialize an empty list (or array) called collected.
  2. Traverse the original doubly linked list from head to tail.
  3. For each node, if its value is not equal to key, append the value to collected.
  4. After traversal, build a new doubly linked list from the values in collected:
    a. For each value, create a new node.
    b. Set the new node's prev to the previously created node.
    c. Set the previous node's next to the new node.
  5. Return the head of the new list (or null if collected is empty).

Code

/*
 * Definition for doubly-linked list node:
 * struct Node {
 *     int data;
 *     Node* next;
 *     Node* prev;
 *     Node(int val) : data(val), next(nullptr), prev(nullptr) {}
 * };
 */

class Solution {
public:
    Node* deleteAllOccurrences(Node* head, int key) {
        // Step 1: Collect all non-key values
        vector<int> collected;
        Node* curr = head;
        while (curr != nullptr) {
            if (curr->data != key) {
                collected.push_back(curr->data);
            }
            curr = curr->next;
        }

        // Step 2: Build a new doubly linked list
        if (collected.empty()) return nullptr;

        Node* newHead = new Node(collected[0]);
        Node* tail = newHead;
        for (int i = 1; i < collected.size(); i++) {
            Node* newNode = new Node(collected[i]);
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }

        return newHead;
    }
};
class Solution:
    def delete_all_occurrences(self, head, key):
        # Step 1: Collect all non-key values
        collected = []
        curr = head
        while curr is not None:
            if curr.data != key:
                collected.append(curr.data)
            curr = curr.next

        # Step 2: Build a new doubly linked list
        if not collected:
            return None

        new_head = Node(collected[0])
        tail = new_head
        for val in collected[1:]:
            new_node = Node(val)
            tail.next = new_node
            new_node.prev = tail
            tail = new_node

        return new_head
/*
 * Definition for doubly-linked list node:
 * class Node {
 *     int data;
 *     Node next;
 *     Node prev;
 *     Node(int val) { data = val; next = null; prev = null; }
 * }
 */

class Solution {
    public Node deleteAllOccurrences(Node head, int key) {
        // Step 1: Collect all non-key values
        List<Integer> collected = new ArrayList<>();
        Node curr = head;
        while (curr != null) {
            if (curr.data != key) {
                collected.add(curr.data);
            }
            curr = curr.next;
        }

        // Step 2: Build a new doubly linked list
        if (collected.isEmpty()) return null;

        Node newHead = new Node(collected.get(0));
        Node tail = newHead;
        for (int i = 1; i < collected.size(); i++) {
            Node newNode = new Node(collected.get(i));
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }

        return newHead;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the entire list once to collect non-key values (O(n)), then iterate through the collected values to build the new list (O(n) in the worst case). Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

We store up to n values in the collected list when no nodes match the key. Additionally, we create up to n brand-new nodes for the output list. This means we use O(n) extra space beyond the original list.

Why This Approach Is Not Efficient

While the brute force runs in O(n) time, it uses O(n) auxiliary space because it creates a completely new list rather than modifying the original one in place.

The problem explicitly asks for O(1) auxiliary space. With n up to 10^5 nodes, allocating a second list of the same size doubles memory usage unnecessarily.

The core waste: doubly linked lists are designed for efficient in-place insertion and deletion. Each node already has prev and next pointers — we can remove any node in O(1) time by simply relinking its neighbors. Building a new list from scratch ignores this fundamental advantage.

Key insight: instead of collecting values and rebuilding, we can walk the original list and snip out matching nodes by adjusting the prev and next pointers of their neighbors. This eliminates all extra space.

Optimal Approach - In-Place Pointer Manipulation

Intuition

Think about removing a person from a line where everyone holds hands with the person in front and behind them. To remove someone, you simply tell the person behind them to hold hands with the person in front of them, and vice versa. The removed person steps out, and the chain stays connected.

In a doubly linked list, removing a node means:

  1. The node before it should point its next to the node after it.
  2. The node after it should point its prev to the node before it.

There are three special cases to handle:

  • Head deletion: If the node to delete is the head, there is no previous node. We simply move the head forward and set the new head's prev to null.
  • Tail deletion: If the node to delete is the last node, there is no next node. We set the previous node's next to null.
  • Middle deletion: The general case — relink both the previous and next neighbors.

We traverse the list once, and whenever we find a node whose value matches the key, we perform the appropriate deletion. This modifies the original list in place without any extra storage.

Step-by-Step Explanation

Let us trace through with DLL: 2 ↔ 2 ↔ 10 ↔ 8 ↔ 4 ↔ 2 ↔ 5 ↔ 2, key = 2:

Step 1: Initialize curr = head (node with value 2). The list is: [2, 2, 10, 8, 4, 2, 5, 2].

Step 2: curr.data = 2, which equals key. This is the head node, so we perform a head deletion.

  • Move head to curr.next (the second node, value 2).
  • Set new head's prev to null.
  • Advance curr to the new head.
  • List is now: [2, 10, 8, 4, 2, 5, 2] with head at the first remaining 2.

Step 3: curr.data = 2, which equals key. This is again the head node.

  • Move head to curr.next (node with value 10).
  • Set new head's prev to null.
  • Advance curr to the new head.
  • List is now: [10, 8, 4, 2, 5, 2] with head at 10.

Step 4: curr.data = 10, which does not equal key. No deletion needed.

  • Simply advance curr to curr.next (node with value 8).

Step 5: curr.data = 8, which does not equal key. No deletion needed.

  • Advance curr to curr.next (node with value 4).

Step 6: curr.data = 4, which does not equal key. No deletion needed.

  • Advance curr to curr.next (node with value 2).

Step 7: curr.data = 2, which equals key. This is a middle node (between 4 and 5).

  • Set curr.prev.next (node 4's next) to curr.next (node 5).
  • Set curr.next.prev (node 5's prev) to curr.prev (node 4).
  • Advance curr to the next node (node 5).
  • List is now: [10, 8, 4, 5, 2].

Step 8: curr.data = 5, which does not equal key. No deletion needed.

  • Advance curr to curr.next (node with value 2).

Step 9: curr.data = 2, which equals key. This is the tail node (curr.next is null).

  • Set curr.prev.next (node 5's next) to null.
  • Advance curr to curr.next, which is null.
  • List is now: [10, 8, 4, 5].

Step 10: curr is null. Traversal complete.

Result: 10 ↔ 8 ↔ 4 ↔ 5

In-Place Deletion — Removing All Occurrences of Key=2 — Watch how we traverse the doubly linked list once, removing each node that matches the key by relinking its neighbors' pointers, without allocating any extra memory.

Algorithm

  1. Set curr to the head of the doubly linked list.
  2. While curr is not null:
    a. If curr.data equals key:
    • Head case: If curr is the head (curr.prev is null), move head to curr.next. If the new head exists, set its prev to null.
    • Tail case: If curr.next is null, set curr.prev.next to null.
    • Middle case: Set curr.prev.next to curr.next, and set curr.next.prev to curr.prev.
    • Save curr.next as nextNode before relinking, then set curr = nextNode.
      b. If curr.data does not equal key:
    • Simply advance: curr = curr.next.
  3. Return the (possibly updated) head.

Code

/*
 * Definition for doubly-linked list node:
 * struct Node {
 *     int data;
 *     Node* next;
 *     Node* prev;
 *     Node(int val) : data(val), next(nullptr), prev(nullptr) {}
 * };
 */

class Solution {
public:
    Node* deleteAllOccurrences(Node* head, int key) {
        Node* curr = head;

        while (curr != nullptr) {
            if (curr->data == key) {
                // Save next before we lose reference
                Node* nextNode = curr->next;

                // If curr is the head
                if (curr->prev == nullptr) {
                    head = nextNode;
                    if (head != nullptr) {
                        head->prev = nullptr;
                    }
                } else {
                    // curr has a previous node
                    curr->prev->next = curr->next;
                    if (curr->next != nullptr) {
                        curr->next->prev = curr->prev;
                    }
                }

                // Move to next node
                curr = nextNode;
            } else {
                curr = curr->next;
            }
        }

        return head;
    }
};
class Solution:
    def delete_all_occurrences(self, head, key):
        curr = head

        while curr is not None:
            if curr.data == key:
                # Save next before relinking
                next_node = curr.next

                # If curr is the head
                if curr.prev is None:
                    head = next_node
                    if head is not None:
                        head.prev = None
                else:
                    # curr has a previous node
                    curr.prev.next = curr.next
                    if curr.next is not None:
                        curr.next.prev = curr.prev

                # Advance to the saved next node
                curr = next_node
            else:
                curr = curr.next

        return head
/*
 * Definition for doubly-linked list node:
 * class Node {
 *     int data;
 *     Node next;
 *     Node prev;
 *     Node(int val) { data = val; next = null; prev = null; }
 * }
 */

class Solution {
    public Node deleteAllOccurrences(Node head, int key) {
        Node curr = head;

        while (curr != null) {
            if (curr.data == key) {
                // Save next before relinking
                Node nextNode = curr.next;

                // If curr is the head
                if (curr.prev == null) {
                    head = nextNode;
                    if (head != null) {
                        head.prev = null;
                    }
                } else {
                    // curr has a previous node
                    curr.prev.next = curr.next;
                    if (curr.next != null) {
                        curr.next.prev = curr.prev;
                    }
                }

                // Advance to the saved next node
                curr = nextNode;
            } else {
                curr = curr.next;
            }
        }

        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the doubly linked list exactly once, visiting each of the n nodes one time. For each node, we perform at most O(1) work: a comparison, and possibly a constant number of pointer updates. The total time is therefore O(n).

Space Complexity: O(1)

We use only a fixed number of pointer variables (curr, nextNode) regardless of the input size. No additional data structures are created. The deletions happen in place by modifying existing pointers, so auxiliary space is constant.