Delete Node in a Linked List

Medium

Microsoft

1 view

Topics:

Linked Lists

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:

The value of the given node should not exist in the linked list.
The number of nodes in the linked list should decrease by one.
All the values before node should be in the same order.
All the values after node should be in the same order.

Custom testing:

For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
We will build the linked list and pass the node to your function.
The output will be the entire list after calling your function.

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Constraints:

The number of the nodes in the given list is in the range [2, 1000].
-1000 <= Node.val <= 1000
The value of each node in the list is unique.
The node to be deleted is in the list and is not a tail node.

Delete Node in a Linked List

Medium

Microsoft

1 view

Topics:

Linked Lists

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:

The value of the given node should not exist in the linked list.
The number of nodes in the linked list should decrease by one.
All the values before node should be in the same order.
All the values after node should be in the same order.

Custom testing:

For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
We will build the linked list and pass the node to your function.
The output will be the entire list after calling your function.

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Constraints:

The number of the nodes in the given list is in the range [2, 1000].
-1000 <= Node.val <= 1000
The value of each node in the list is unique.
The node to be deleted is in the list and is not a tail node.

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:

Can I assume the given node is definitely present in the linked list, and is not the tail node?
Can the value of the node to be deleted be null or empty?
What is the data type of the 'node' value? Can I assume it will always be an integer?
Is the linked list singly or doubly linked? I am assuming singly linked.
Is it possible that the linked list contains cycles?

Brute Force Solution

Approach

The brute force method for removing a node in a linked list involves searching for the node we want to get rid of by looking at each node one by one from the beginning. Once found, we rearrange connections to bypass the unwanted node. The brute force method would not generally be used for this problem because we are given access to the node to delete.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
Check each node in the list to see if it's the node we want to remove.
If we find the node, change the 'next' connection of the node before it to point to the node after the one we're removing, effectively skipping over the node we want to get rid of.
If we reach the end of the list without finding the node, it means the node isn't in the list, and we don't need to do anything.

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 head is None:
        return None

    # If the node to delete is the head, update the head
    if head == node_to_delete:
        head = head.next_node
        return head

    current_node = head

    # Iterate until the end of the list.
    while current_node is not None:
        # Find the node before the node to delete.
        if current_node.next_node == node_to_delete:
            # Skip the node to be deleted.

            current_node.next_node = node_to_delete.next_node

            return head

        current_node = current_node.next_node

    return head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list, at most, once. In the worst-case scenario, the node to be deleted is the last node in the list, requiring traversal of all n nodes to find its predecessor and update the next pointer. Therefore, the time complexity is linearly proportional to the number of nodes in the list, resulting in O(n).

Space Complexity

O(1) – The provided algorithm iterates through the linked list to find the node to delete. It does not create any additional data structures such as auxiliary arrays, hash maps, or lists. Only a constant number of pointer variables are used for traversal and manipulation of the linked list, independent of the size of the list, N. Therefore, the algorithm uses constant auxiliary space.

Optimal Solution

Approach

Since we are given the node to delete and not the head of the list, we cannot traverse to find the node before the one we want to delete. Instead, we'll overwrite the node to be deleted with the contents of the next node, then bypass the next node, effectively deleting it.

Here's how the algorithm would work step-by-step:

Replace the value of the node we want to delete with the value of the node that comes right after it.
Point the node we want to delete to skip over the next node, pointing it to the node after the next one.

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 the value from the next node to the node to be deleted.
    node_to_delete.value = node_to_delete.next_node.value

    # Update the next pointer to skip the actual next node.
    node_to_delete.next_node = node_to_delete.next_node.next_node

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The provided solution involves overwriting the value of the given node with the value of the next node and then updating the next pointer of the given node to skip the next node. These operations are performed directly on the given node and its immediate successor, regardless of the overall size 'n' of the linked list. Therefore, the time complexity is constant.

Space Complexity

O(1) – The algorithm modifies the linked list in-place by overwriting the value and next pointer of the target node. No auxiliary data structures like arrays, hash maps, or additional linked lists are created. Therefore, the algorithm uses a constant amount of extra space, independent of the number of nodes N in the linked list.

Edge Cases

Case	How to Handle
Node is null	While the problem states the node to delete is given, a null node should raise an IllegalArgumentException.
Node is the tail of the list	Copy the value from node.next to node and then set node.next to null.
Node to delete is the only node in the list	This scenario is technically impossible based on the problem description, but if encountered, one approach could be to set the node's value to null; however, a proper solution would be to raise an exception because you can't delete the only node if you don't have the head pointer.
List contains only two nodes and node is the first node	Copy the value from node.next into node and then set node.next to null, effectively removing the second node.
Large list: Check for potential memory issues (though unlikely with this algorithm)	The algorithm operates in-place and has O(1) space complexity, so memory is unlikely to be an issue even for large lists.
Values stored in the list are of different types (e.g., int, string, object)	The algorithm works regardless of the type of data stored in the nodes as it only swaps the values and pointers and doesn't perform calculations.
Node is not actually in the linked list	Since we don't have the head, we can't verify this; either this is considered invalid input, or no operation is performed if node.next is null as described in another case.
List has cycles which can cause infinite loop.	Singly linked lists should not contain cycles, but if one exists it would cause an infinite loop; checking for cycles is generally beyond the scope of this problem but a time out would prevent a true infinite loop.