algoadvance

LeetCode Problem 237: Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Suppose the linked list is [4,5,1,9] and you are given the node having value 5, the linked list should become [4,1,9] after calling your function.

Clarifying Questions

  1. Q: Can I assume that the input node is not the tail node?
    • A: Yes, you can assume the node given is not the tail node.
  2. Q: What should be the return type of this function?
    • A: The function should return None since the deletion is done in place.
  3. Q: Is it allowed to modify the values of the given nodes?
    • A: Yes, you are allowed to copy the value of the next node to the current node and then delete the next node.

Strategy

To delete a node given only access to that node in a singly linked list:

  1. Copy the value from the next node to the current node (effectively overwriting the current node’s value).
  2. Change the current node’s next pointer to skip the next node (effectively removing it from the list).

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteNode(node):
    """
    Delete the given node in a singly linked list.
    
    Parameters:
    node (ListNode): The node to be deleted.

    Returns:
    void: Does not return anything, modifies the list in place.
    """
    if node is None or node.next is None:
        raise ValueError("The node to be deleted cannot be the tail node and must not be null.")
    
    # Copy the next node's value to this node
    node.val = node.next.val
    # Bypass the next node
    node.next = node.next.next

Time Complexity

The time complexity is (O(1)) because the operation involves a constant amount of work:

  1. Copying the value from the next node.
  2. Re-pointing the next pointer of the current node.

This makes the solution highly efficient, since the number of operations does not depend on the length of the linked list.

Note

This problem is unique in that it takes advantage of the properties of singly linked lists to bypass the usual requirements of knowing the previous node or traversing the list from the head.

Try our interview co-pilot at AlgoAdvance.com