Delete Node in a Linked List
Medium
You are given a singly-linked list and a specific node within it that you need to delete. However, you do not have access to the head of the list; you are only given the node to be deleted directly. All values in the linked list are guaranteed to be unique, and the node you are asked to delete is guaranteed to not be the last node in the list.
Your task is to implement a function that deletes the given node from the linked list. Note that "deleting" here means that the value of the given node should no longer exist in the linked list, the number of nodes in the linked list should decrease by one, all values before the deleted node should remain in the same order, and all values after the deleted node should also remain in the same order.
For example:
- If the linked list is
4 -> 5 -> 1 -> 9and you are given the node with value5to delete, the linked list should become4 -> 1 -> 9after your function is called. - If the linked list is
4 -> 5 -> 1 -> 9and you are given the node with value1to delete, the linked list should become4 -> 5 -> 9after your function is called.
How would you approach this problem, considering the constraint of not having access to the head of the list?
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- Could the linked list be empty, even though the target node isn't the tail?
- What is the range of possible values for the node's data?
- Is the input node guaranteed to be in the list?
- Can I assume the 'next' pointer of the node to be deleted is not null?
- What is the desired behavior if, hypothetically, the input node was the tail of the list, even though the problem states it won't be?
Brute Force Solution
Approach
The goal is to remove a specific item from a chain of items. We'll achieve this by going through the chain and finding the item to remove. When we find it, we'll rearrange the chain to exclude it.
Here's how the algorithm would work step-by-step:
- Start at the beginning of the chain of items.
- Look at each item in the chain, one by one, until you find the specific item you want to remove.
- Once you find the item, take the item before it and connect it to the item after the one you're removing. This effectively skips over the item to be deleted.
- That's it! The item is now removed from the chain.
Code Implementation
class ListNode:
def __init__(self, value=0, next_node=None):
self.value = value
self.next_node = next_node
def delete_node_brute_force(head, node_to_delete):
# If the node to delete is the head, update the head.
if head == node_to_delete:
head = node_to_delete.next_node
return head
current_node = head
# Traverse the linked list to find the node before the one to delete.
while current_node.next_node != node_to_delete:
current_node = current_node.next_node
# Once we locate node, rewire next node.
if current_node.next_node == node_to_delete:
current_node.next_node = node_to_delete.next_node
return headBig(O) Analysis
Optimal Solution
Approach
The challenge here is to remove a node from a linked list, but we are given direct access only to that node and not the node before it. The clever trick is to copy the data from the next node into the node we want to delete, and then bypass the next node. This effectively removes the target node from the list.
Here's how the algorithm would work step-by-step:
- Take the information from the node that comes directly after the node you want to remove.
- Copy that information into the node that you want to remove. Think of it as replacing the node with its neighbor.
- Now, bypass the next node. The node you wanted to remove will now point to the node after the original 'next' node. This skips over the original 'next' node, effectively removing it from the list.
Code Implementation
class ListNode:
def __init__(self, value=0, next_node=None):
self.value = value
self.next_node = next_node
def delete_node(node_to_delete):
# Copy value from the next node
node_to_delete.value = node_to_delete.next_node.value
# Update 'next' pointer to skip the next node
# Effectively deleting the node
node_to_delete.next_node = node_to_delete.next_node.next_nodeBig(O) Analysis
Edge Cases
| Case | How to Handle |
|---|---|
| Null node input | Throw IllegalArgumentException or return null to signal an invalid input node. |
| Node is the last node (tail) in the list | The problem statement explicitly states that the given node is not the tail, so we don't handle it, but it is important to reiterate this as part of assumptions |
| List contains only one node (which is the node to delete) | Problem states node is not the tail, which implies more than 1 node is present, but reiterating the assumption is crucial. |
| Very large linked list to test scalability | The algorithm operates in O(1) time and constant space, making it scale efficiently regardless of list size. |
| Node to be deleted is the head of the linked list | The algorithm works regardless of whether the node to delete is the head; no special handling required. |
| Memory constraints prevent creating a copy of the next node | The problem assumes sufficient memory for copying the next node's data. |
| Linked list contains cycles | The standard algorithm doesn't explicitly handle cycles, and might behave unexpectedly if a cycle exists; the problem implies a singly linked list without cycles. |
| Deleting a node with identical value as the next node | The algorithm works correctly even if the node to be deleted has same value as the next node since only the *data* field is copied. |
