Delete Node in a Linked List

Problem Statement

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Input/Output Specifications

• Input: The node to be deleted (not the head)
• Output: None (modify the list in-place)
• Constraints:
  • The number of nodes in the 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

Examples

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.

Solutions

Approach: Copy Next Node’s Value and Delete Next

Since we don’t have access to the previous node, we can’t directly delete the current node. Instead, we copy the value from the next node and then delete the next node.

Algorithm:

1. Copy the value from the next node to the current node
2. Store reference to the next node
3. Update current node’s next pointer to skip the next node
4. The next node is effectively “deleted” from the list

Python:

def deleteNode(node):
    """
    Delete a node when you only have access to that node
    Time: O(1)
    Space: O(1)
    """
    # Copy the value from the next node
    node.val = node.next.val
    
    # Delete the next node
    node.next = node.next.next

Java:

class Solution {
    /**
     * Delete a node when you only have access to that node
     * Time: O(1)
     * Space: O(1)
     */
    public void deleteNode(ListNode node) {
        // Copy the value from the next node
        node.val = node.next.val;
        
        // Delete the next node
        node.next = node.next.next;
    }
}

Go:

// deleteNode - Delete a node when you only have access to that node
// Time: O(1)
// Space: O(1)
func deleteNode(node *ListNode) {
    // Copy the value from the next node
    node.Val = node.Next.Val
    
    // Delete the next node
    node.Next = node.Next.Next
}

JavaScript:

/**
 * Delete a node when you only have access to that node
 * Time: O(1)
 * Space: O(1)
 */
function deleteNode(node) {
    // Copy the value from the next node
    node.val = node.next.val;
    
    // Delete the next node
    node.next = node.next.next;
}

C#:

public class Solution {
    /// <summary>
    /// Delete a node when you only have access to that node
    /// Time: O(1)
    /// Space: O(1)
    /// </summary>
    public void DeleteNode(ListNode node) {
        // Copy the value from the next node
        node.val = node.next.val;
        
        // Delete the next node
        node.next = node.next.next;
    }
}

Key Insights

• No access to previous node: We can’t modify the previous node’s next pointer
• Copy and delete strategy: Copy the next node’s value and delete the next node
• Constant time operation: This approach works in O(1) time
• Constraint utilization: The problem guarantees the node is not a tail node
• In-place modification: We modify the existing list structure

Edge Cases

• The node to delete is the second-to-last node
• The node to delete is somewhere in the middle
• The node to delete is the head (not applicable due to constraints)
• The node to delete is the tail (not applicable due to constraints)

Test Cases

# Test case 1: Delete middle node
head = ListNode(4)
head.next = ListNode(5)
head.next.next = ListNode(1)
head.next.next.next = ListNode(9)

node_to_delete = head.next  # Node with value 5
deleteNode(node_to_delete)
# Expected: [4,1,9]

# Test case 2: Delete second-to-last node
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
head2.next.next.next = ListNode(4)

node_to_delete2 = head2.next.next  # Node with value 3
deleteNode(node_to_delete2)
# Expected: [1,2,4]

Follow-up Questions

• What if the node to delete is the tail node?
• How would you handle this if you had access to the head?
• What if you need to delete multiple nodes?
• How would you implement this for a doubly linked list?

Common Mistakes

• Trying to delete the current node directly (impossible without previous node)
• Not copying the value before deleting the next node
• Forgetting that we’re actually deleting the next node, not the current one
• Not understanding the constraint that the node is not a tail node
• Memory leaks when not properly handling the deleted node

Important Notes

• This is a “tricky” problem that tests understanding of linked list operations
• The node being “deleted” is actually replaced by the next node’s value
• This approach only works because we’re guaranteed the node is not a tail node
• The actual node object passed to the function is not deleted from memory
• This is a common interview question that tests problem-solving creativity