Delete all occurrences of a key in DLL

Intuition

Go through each and every node of the doubly linked list and delete the node which matches the target/key value.

Approach

Start by setting a temporary pointer to the head of the doubly linked list. This pointer will be used to traverse the list.
Loop through the list until the end is reached. For each node, check if its value equals the target value to be deleted.
Delete Target Nodes:
- If the node's value matches the target:
  - If the node is the head of the list, update the head to the next node.
  - Update the next pointer of the previous node (if it exists) to skip the current node.
  - Update the prev pointer of the next node (if it exists) to skip the current node.
  - Delete the current node and move the temporary pointer to the next node.
- If the node's value does not match the target, move the temporary pointer to the next node.
After the traversal, return the updated head of the list, which may have been modified if the head node was deleted.

Dry Run

Solution

#include <bits/stdc++.h>

using namespace std;

// Definition of doubly linked list
struct ListNode {
    int val;
    ListNode* next;
    ListNode* prev;
    ListNode() {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode* next1, ListNode* prev1) {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

class Solution {
public:
    // Function to delete all occurrences of a target value
    ListNode* deleteAllOccurrences(ListNode* head, int target) {
        ListNode* temp = head;
        
        while (temp != NULL) {
            if (temp->val == target) {
                // Update head if needed
                if (temp == head) {
                    head = temp->next;
                }
                
                ListNode* nextNode = temp->next;
                ListNode* prevNode = temp->prev;

                // Update previous node's next
                if (nextNode != NULL) {
                    nextNode->prev = prevNode;
                }
                
                // Update next node's previous
                if (prevNode != NULL) {
                    prevNode->next = nextNode;
                }

                // Delete the current node
                delete temp;
                temp = nextNode;
            } else {
                temp = temp->next;
            }
        }
        
        return head;
    }
};

// Function to print doubly linked list
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

// Helper function to create a new node
ListNode* newNode(int data) {
    ListNode* node = new ListNode(data);
    return node;
}

int main() {
    // Creating doubly linked list
    ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->prev = head;
    head->next->next = newNode(3);
    head->next->next->prev = head->next;
    head->next->next->next = newNode(2);
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = newNode(4);
    head->next->next->next->next->prev = head->next->next->next;
    head->next->next->next->next->next = newNode(2);
    head->next->next->next->next->next->prev = head->next->next->next->next;
    head->next->next->next->next->next->next = newNode(5);
    head->next->next->next->next->next->next->prev = head->next->next->next->next->next;

    // Print original list
    cout << "Original list: ";
    printList(head);

    // Delete all occurrences of 2
    Solution sol;
    head = sol.deleteAllOccurrences(head, 2);

    // Print modified list
    cout << "Modified list: ";
    printList(head);

    return 0;
}
import java.util.*;

// Definition of doubly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode prev;
    ListNode() {
        val = 0;
        next = null;
        prev = null;
    }
    ListNode(int data1) {
        val = data1;
        next = null;
        prev = null;
    }
    ListNode(int data1, ListNode next1, ListNode prev1) {
        val = data1;
        next = next1;
        prev = prev1;
    }
}

class Solution {
    // Function to delete all occurrences of a target value
    public ListNode deleteAllOccurrences(ListNode head, int target) {
        ListNode temp = head;

        while (temp != null) {
            if (temp.val == target) {
                // Update head if needed
                if (temp == head) {
                    head = temp.next;
                }

                ListNode nextNode = temp.next;
                ListNode prevNode = temp.prev;

                // Update previous node's next
                if (nextNode != null) {
                    nextNode.prev = prevNode;
                }

                // Update next node's previous
                if (prevNode != null) {
                    prevNode.next = nextNode;
                }

                // Delete the current node
                temp = nextNode;
            } else {
                temp = temp.next;
            }
        }

        return head;
    }
}

// Function to print doubly linked list
public class Main {
    public static void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    // Helper function to create a new node
    public static ListNode newNode(int data) {
        return new ListNode(data);
    }

    public static void main(String[] args) {
        // Creating doubly linked list
        ListNode head = newNode(1);
        head.next = newNode(2);
        head.next.prev = head;
        head.next.next = newNode(3);
        head.next.next.prev = head.next;
        head.next.next.next = newNode(2);
        head.next.next.next.prev = head.next.next;
        head.next.next.next.next = newNode(4);
        head.next.next.next.next.prev = head.next.next.next;
        head.next.next.next.next.next = newNode(2);
        head.next.next.next.next.next.prev = head.next.next.next.next;
        head.next.next.next.next.next.next = newNode(5);
        head.next.next.next.next.next.next.prev = head.next.next.next.next.next;

        // Print original list
        System.out.print("Original list: ");
        printList(head);

        // Delete all occurrences of 2
        Solution sol = new Solution();
        head = sol.deleteAllOccurrences(head, 2);

        // Print modified list
        System.out.print("Modified list: ");
        printList(head);
    }
}
# Definition of doubly linked list
class ListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

class Solution:
    # Function to delete all occurrences of a target value
    def deleteAllOccurrences(self, head, target):
        temp = head
        
        while temp is not None:
            if temp.val == target:
                # Update head if needed
                if temp == head:
                    head = temp.next
                
                nextNode = temp.next
                prevNode = temp.prev

                # Update previous node's next
                if nextNode is not None:
                    nextNode.prev = prevNode
                
                # Update next node's previous
                if prevNode is not None:
                    prevNode.next = nextNode

                # Delete the current node
                temp = nextNode
            else:
                temp = temp.next
        
        return head

# Function to print doubly linked list
def printList(head):
    temp = head
    while temp is not None:
        print(temp.val, end=" ")
        temp = temp.next
    print()

# Helper function to create a new node
def newNode(data):
    return ListNode(data)

if __name__ == "__main__":
    # Creating doubly linked list
    head = newNode(1)
    head.next = newNode(2)
    head.next.prev = head
    head.next.next = newNode(3)
    head.next.next.prev = head.next
    head.next.next.next = newNode(2)
    head.next.next.next.prev = head.next.next
    head.next.next.next.next = newNode(4)
    head.next.next.next.next.prev = head.next.next.next
    head.next.next.next.next.next = newNode(2)
    head.next.next.next.next.next.prev = head.next.next.next.next
    head.next.next.next.next.next.next = newNode(5)
    head.next.next.next.next.next.next.prev = head.next.next.next.next.next

    # Print original list
    print("Original list: ", end="")
    printList(head)

    # Delete all occurrences of 2
    sol = Solution()
    head = sol.deleteAllOccurrences(head, 2)

    # Print modified list
    print("Modified list: ", end="")
    printList(head)
// Definition of doubly linked list
class ListNode {
    constructor(val = 0, next = null, prev = null) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class Solution {
    // Function to delete all occurrences of a target value
    deleteAllOccurrences(head, target) {
        let temp = head;

        while (temp !== null) {
            if (temp.val === target) {
                // Update head if needed
                if (temp === head) {
                    head = temp.next;
                }

                let nextNode = temp.next;
                let prevNode = temp.prev;

                // Update previous node's next
                if (nextNode !== null) {
                    nextNode.prev = prevNode;
                }

                // Update next node's previous
                if (prevNode !== null) {
                    prevNode.next = nextNode;
                }

                // Move to the next node
                temp = nextNode;
            } else {
                temp = temp.next;
            }
        }

        return head;
    }
}

// Function to print doubly linked list
function printList(head) {
    let temp = head;
    while (temp !== null) {
        process.stdout.write(temp.val + " ");
        temp = temp.next;
    }
    console.log();
}

// Helper function to create a new node
function newNode(data) {
    return new ListNode(data);
}

(function() {
    // Creating doubly linked list
    let head = newNode(1);
    head.next = newNode(2);
    head.next.prev = head;
    head.next.next = newNode(3);
    head.next.next.prev = head.next;
    head.next.next.next = newNode(2);
    head.next.next.next.prev = head.next.next;
    head.next.next.next.next = newNode(4);
    head.next.next.next.next.prev = head.next.next.next;
    head.next.next.next.next.next = newNode(2);
    head.next.next.next.next.next.prev = head.next.next.next.next;
    head.next.next.next.next.next.next = newNode(5);
    head.next.next.next.next.next.next.prev = head.next.next.next.next.next;

    // Print original list
    process.stdout.write("Original list: ");
    printList(head);

    // Delete all occurrences of 2
    let sol = new Solution();
    head = sol.deleteAllOccurrences(head, 2);

    // Print modified list
    process.stdout.write("Modified list: ");
    printList(head);
})();

Complexity Analysis

Time Complexity: O(N) because the linked list is traversed only once. Here, N represents the number of nodes in the linked list.
Space Complexity: O(1) because no extra space used.

Problem List

Delete all occurrences of a key in DLL

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code