712304. Delete all occurrences of a given key in a doubly linked list
Delete all occurrences of a given key in a doubly linked list
Summary
Delete all occurrences of a given key in a doubly linked list. The problem requires you to traverse the list and remove all nodes that have the specified key.
Detailed Explanation
To solve this problem, we will use a simple traversal algorithm and remove each node that has the given key. We will start from one end of the list and move towards the other end, removing any nodes that match the target key.
Here is a step-by-step breakdown of the solution:
- Start at one end of the doubly linked list.
- Traverse the list until you reach the other end.
- For each node in the list:
- Check if the node's value matches the target key.
- If it does, remove the node from the list.
To remove a node from the list, we will need to update the prev and next pointers of its neighboring nodes.
Here is an ASCII art diagram representing the doubly linked list:
Node 1 <-> Node 2 <-> ... <-> Node N
Time complexity: O(n), where n is the number of nodes in the list. This is because we are traversing the entire list once and removing each node that matches the target key.
Space complexity: O(1), as we are only using a constant amount of space to store the current node and the target key.
Optimized Solutions
Java
public void deleteKey(DoublyLinkedList list, int key) {
Node current = list.head;
while (current != null) {
if (current.data == key) {
removeNode(current);
}
current = current.next;
}
}
private void removeNode(Node node) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
list.head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
list.tail = node.prev;
}
}