Given head of a doubly linked list and an integer key, delete every node whose data equals key. Return the head of the modified doubly linked list.
A doubly linked list node contains three parts: data, previous pointer, and next pointer. Deletion must preserve correct forward and backward links after removing matching nodes from the beginning, middle, or end.
Example 1
Input: DLL = [10, 4, 10, 5, 10], key = 10
Output: [4, 5]
Explanation: Nodes containing 10 are removed. Remaining nodes keep valid previous and next links.
Example 2
Input: DLL = [2, 2, 2], key = 2
Output: []
Explanation: Every node matches key, so the final list becomes empty.
Approach
Traverse the doubly linked list once and process every node independently. Whenever node data matches key, store the next node before deletion, then reconnect previous and next neighbors around the matching node.
Head updates need special care because deleting the first node changes the entry point of the list. Tail deletion also needs correct handling because the next pointer becomes null.
Algorithm
Initialize
currentwithheadand traverse whilecurrentis notNULL, as every node needs to be checked for the givenkey.Store
current->nextinnextNodebefore changing any links, as the original next node is needed to continue traversal after the current node is removed.Check whether
current->dataequalskey, since a matching value identifies the node that needs to be deleted.Update
headtocurrent->nextwhen the matching node is the head, as removing the first node makes the next node the new beginning of the list.Connect
current->prev->nexttocurrent->nextwhen a previous node exists, which bypasses the current node from the forward direction.Connect
current->next->prevtocurrent->prevwhen a next node exists, which keeps the backward links connected after deletion.Move
currenttonextNode, as the saved pointer preserves access to the remaining list after the current node's links have been changed.Return
headafter the traversal ends, as all nodes containing the givenkeyhave been removed while the remaining doubly linked list stays connected.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* prev; Node* next; // Constructor for doubly linked list node. Node(int value) { data = value; prev = nullptr; next = nullptr; }};class Solution {public: // Deletes every node whose value equals the given key. Node* deleteAllOccurOfX(Node* head, int key) { Node* current = head; while (current != nullptr) { // Save the next node before modifying links. Node* nextNode = current->next; if (current->data == key) { // Update head if the first node is deleted. if (current == head) { head = current->next; } // Connect previous node with next node. if (current->prev != nullptr) { current->prev->next = current->next; } // Connect next node with previous node. if (current->next != nullptr) { current->next->prev = current->prev; } // Delete the current node. delete current; } // Move to the next node. current = nextNode; } return head; }};// Builds a doubly linked list from array values.Node* buildList(vector<int>& values) { if (values.empty()) { return nullptr; } Node* head = new Node(values[0]); Node* tail = head; for (int index = 1; index < (int)values.size(); index++) { // Create and attach a new node. Node* newNode = new Node(values[index]); tail->next = newNode; newNode->prev = tail; // Move tail forward. tail = newNode; } return head;}// Prints the doubly linked list.void printList(Node* head) { Node* current = head; while (current != nullptr) { cout << current->data << " "; current = current->next; } cout << endl;}// Driver code.int main() { vector<int> values = {10, 4, 10, 5, 10}; int key = 10; Node* head = buildList(values); Solution solution; head = solution.deleteAllOccurOfX(head, key); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), every node is visited once during the traversal, where N is the total number of nodes in the linked list.
Space Complexity: O(1), only a constant number of pointer variables are used, regardless of N.
Interview follow-up Questions
Yes. When the head node matches key, head must move to the next node and the new head previous pointer must become null through relinking.
Be the first to add a comment.