700429. Delete keys in a Linked list
Delete keys in a Linked list
Slug: delete-keys-in-a-linked-list Difficulty: Medium Id: 700429
Summary
Delete keys in a linked list is a common problem that involves traversing through a singly linked list and removing nodes with specific key values. This task requires attention to the pointers of the adjacent nodes and careful handling of edge cases to ensure the integrity of the list.
Detailed Explanation
The approach to solving this problem is straightforward - traverse through the linked list, check each node's value against the target key, and remove any matching nodes. However, a crucial aspect to consider is how to maintain the correct pointers after removing a node.
Here's a step-by-step breakdown of the solution:
- Initialize a variable
prevto null, which will keep track of the previous node as we traverse. - Start traversing through the linked list, comparing each node's value with the target key.
- If the current node's value matches the target key:
- Update
prevto point to the current node if it's not null. This ensures that the next node remains unaffected by the removal. - Set the current node's
nextpointer to skip over the node being removed, effectively "jumping" to the next node in the list. - If
previs not null, update itsnextpointer to point to the current node (now pointing to the node after the one that was just removed).
- Update
- Repeat steps 2-3 until the end of the linked list.
Time complexity: O(n), where n is the number of nodes in the list. Space complexity: O(1), as we only use a few extra variables for temporary storage.
Optimized Solutions
Java
public static void deleteKey(Node head, int key) {
Node current = head;
Node prev = null;
while (current != null) {
if (current.data == key) {
if (prev == null) {
head = current.next;
} else {
prev.next = current.next;
}
} else {
prev = current;
}
current = current.next;
}
}