Delete Node in a Linked List

Medium

Google

1 view

Topics:

Linked Lists

You are given a singly-linked list where each node contains a unique integer value. You are also given a specific node within the list. Your task is to delete this given node from the linked list, but with a crucial constraint: you do not have access to the head of the linked list. You only have a reference to the node that needs to be deleted.

Here are the specific requirements:

The linked list is singly-linked.
Each node in the list contains a unique integer value.
You are given the node to be deleted; you are not given access to the head of the list.
The node to be deleted is guaranteed not to be the last node (tail) of the list.
You must modify the list such that the value of the given node is effectively removed, the number of nodes decreases by one, and the order of the remaining nodes is preserved.

Consider the following examples:

Example 1:

Linked List: 4 -> 5 -> 1 -> 9
Node to delete: The node with value 5
Expected Output: 4 -> 1 -> 9

Example 2:

Linked List: 1 -> 2 -> 3 -> 4
Node to delete: The node with value 2
Expected Output: 1 -> 3 -> 4

Explain your approach to solve this problem, considering the constraint that you don't have access to the head of the list. Write a function that takes the node to be deleted as input and modifies the linked list accordingly. Also, consider the time and space complexity of your solution.

Delete Node in a Linked List

Medium

Google

1 view

Topics:

Linked Lists

You are given a singly-linked list where each node contains a unique integer value. You are also given a specific node within the list. Your task is to delete this given node from the linked list, but with a crucial constraint: you do not have access to the head of the linked list. You only have a reference to the node that needs to be deleted.

Here are the specific requirements:

The linked list is singly-linked.
Each node in the list contains a unique integer value.
You are given the node to be deleted; you are not given access to the head of the list.
The node to be deleted is guaranteed not to be the last node (tail) of the list.
You must modify the list such that the value of the given node is effectively removed, the number of nodes decreases by one, and the order of the remaining nodes is preserved.

Consider the following examples:

Example 1:

Linked List: 4 -> 5 -> 1 -> 9
Node to delete: The node with value 5
Expected Output: 4 -> 1 -> 9

Example 2:

Linked List: 1 -> 2 -> 3 -> 4
Node to delete: The node with value 2
Expected Output: 1 -> 3 -> 4

Explain your approach to solve this problem, considering the constraint that you don't have access to the head of the list. Write a function that takes the node to be deleted as input and modifies the linked list accordingly. Also, consider the time and space complexity of your solution.

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 head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list to find the node to delete. In the worst-case scenario, the node to be deleted is at the end of the list or not present at all, requiring traversal of all n nodes. Therefore, the time complexity is directly proportional to the number of nodes, n, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided plain English explanation for deleting a node in a linked list involves traversing the list and rearranging pointers. It does not describe the creation of any auxiliary data structures like arrays, hash maps, or additional linked lists. The algorithm only needs to keep track of a few pointers (e.g., the current node and the previous node) to update the links. Therefore, the space required remains constant regardless of the size of the linked list, denoted as N. Hence, the space complexity is O(1).

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_node

Big(O) Analysis

Time Complexity

O(1) – The provided algorithm involves only copying data from the next node to the node to be deleted and then adjusting the 'next' pointer. These operations take a fixed amount of time regardless of the size of the linked list. Thus, the time complexity is constant, or O(1).

Space Complexity

O(1) – The algorithm only modifies the values and pointer of the given node and its immediate successor. No additional data structures, like arrays, hash maps, or stacks are created that scale with the size of the linked list (N, where N is the number of nodes in the list). The operations described involve only a constant amount of extra space, regardless of the size of the input list, leading to a constant space complexity.

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.