700131. Delete in a Doubly Linked List
Easy
Delete Node in a Doubly Linked List
Summary
This problem involves deleting a node from a doubly linked list. A doubly linked list is a data structure where each node has two pointers, one pointing to the previous node and another pointing to the next node. The goal is to delete a given node from the list while maintaining the integrity of the remaining nodes.
Detailed Explanation
To solve this problem, we will follow these steps:
- Find the node: First, locate the node that needs to be deleted in the doubly linked list.
- Update previous node's next pointer: Update the
nextpointer of the previous node to point to the node that was previously pointed to by the current node. - Update current node's next pointer: Set the
nextpointer of the current node tonull. - Update node that was previously pointed to: Set the
previouspointer of the node that was previously pointed to by the current node to point to the previous node. - Delete the node: Finally, delete the current node.
Here is a step-by-step breakdown of the algorithm:
// Given a doubly linked list and a target node
Node* deleteNode(Node* head, Node* target) {
// If the target node is the head of the list
if (head == target) {
return head->next; // Return the new head
}
// Traverse the list to find the target node
Node* current = head;
while (current != null && current != target) {
current = current->next;
}
// If the target node is not found in the list
if (current == null) {
return head; // Return the original head
}
// Update previous node's next pointer
Node* previous = head;
while (previous->next != target) {
previous = previous->next;
}
previous->next = current->next;
// Update current node's next pointer and delete it
current->next = null;
return head; // Return the modified list
}
The time complexity of this algorithm is O(n), where n is the number of nodes in the doubly linked list. The space complexity is O(1), as we only use a constant amount of space to store the pointers and variables.
Optimized Solutions
Java
public class DoublyLinkedList {
public static Node deleteNode(Node head, Node target) {
if (head == target) {
return head.next;
}
Node current = head;
while (current != null && current != target) {
current = current.next;
}
if (current == null) {
return head;
}
Node previous = head;
while (previous.next != target) {
previous = previous.next;
}
previous.next = current.next;
current.next = null;
return head;
}
}