Facebook Pixel

237. Delete Node in a Linked List

Problem Description

This problem asks you to delete a node from a singly-linked list with an unusual constraint: you're only given access to the node that needs to be deleted, not the head of the list.

In a typical linked list deletion, you would traverse from the head to find the node before the target node, then update pointers to skip over the target. However, in this problem, you cannot access any previous nodes.

Given constraints:

  • You have direct access only to the node that should be deleted
  • The node is guaranteed not to be the last node in the list
  • All values in the linked list are unique
  • You cannot actually remove the node from memory

The deletion requirements:

  • The value of the given node should no longer exist in the linked list
  • The total number of nodes should decrease by one
  • The order of all other values should remain unchanged

The solution leverages a clever trick: instead of actually deleting the given node, you copy the value from the next node into the current node, then bypass the next node. This effectively "deletes" the current node's value from the list.

For example, if you have a list 4 -> 5 -> 1 -> 9 and need to delete the node with value 5:

  1. Copy the value 1 from the next node into the current node: 4 -> 1 -> 1 -> 9
  2. Update the pointer to skip the next node: 4 -> 1 -> 9

The implementation simply does:

  • node.val = node.next.val - copies the next node's value
  • node.next = node.next.next - bypasses the next node
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight comes from recognizing what we can and cannot do with our constraints. Since we only have access to the node to be deleted and no access to previous nodes, we cannot perform a traditional deletion where we update the previous node's next pointer to skip the current node.

Let's think about what defines a node's identity in the linked list. Is it the physical node object itself, or is it the value it contains? From the list's perspective, what matters is the sequence of values. If we can make it appear that a particular value has been removed from the sequence, we've effectively "deleted" that node.

This leads to a critical realization: instead of trying to remove the current node (which would require access to the previous node), we can transform the current node into a copy of the next node, and then remove the next node instead. Since we have access to the next node through node.next, this operation is possible.

Think of it like a line of people where each person holds a number. If we need to remove person B who is between persons A and C, but we can only interact with person B, we can:

  1. Have person B take person C's number
  2. Have person B point to whoever person C was pointing to
  3. Now person B has effectively become person C, and the original person B's number has disappeared from the line

This works because:

  • We're guaranteed the node isn't the last one (so node.next always exists)
  • We can modify both the value and the pointer of the current node
  • The end result is indistinguishable from actually deleting the node - the value disappears and the list becomes one node shorter

Solution Approach

The solution implements the node assignment technique, which is a clever way to delete a node when we only have access to that node itself.

The implementation consists of two simple operations:

  1. Copy the next node's value: node.val = node.next.val

    • This overwrites the current node's value with the value from the next node
    • After this step, the current node effectively becomes a duplicate of the next node
  2. Bypass the next node: node.next = node.next.next

    • This updates the current node's pointer to skip over the next node
    • The next node is now disconnected from the list

Let's trace through an example to see how this works:

  • Original list: 4 -> 5 -> 1 -> 9, where we want to delete the node with value 5
  • After node.val = node.next.val: The list becomes 4 -> 1 -> 1 -> 9 (the node that had 5 now has 1)
  • After node.next = node.next.next: The list becomes 4 -> 1 -> 9 (the second 1 node is bypassed)

The beauty of this approach is its simplicity - it achieves the deletion in O(1) time complexity with just two assignment statements. No traversal is needed, and no additional data structures are required.

This pattern works because:

  • We're guaranteed node.next exists (the node is not the last one)
  • We can modify the node in-place
  • The linked list structure is maintained correctly after the operation
  • From an external perspective, the desired value has been removed from the list

The space complexity is O(1) as we only use the existing node references without allocating any additional memory.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to understand how this solution works.

Initial Setup: Suppose we have a linked list: 2 -> 7 -> 4 -> 3 and we need to delete the node with value 7. We are given direct access only to the node containing 7.

Step 1: Initial State

2 -> 7 -> 4 -> 3
     ^
   (node)
  • node.val = 7
  • node.next points to the node with value 4
  • node.next.next points to the node with value 3

Step 2: Copy Next Node's Value Execute: node.val = node.next.val

2 -> 4 -> 4 -> 3
     ^
   (node)
  • We copy the value 4 from the next node into our current node
  • Now the node that originally contained 7 contains 4
  • We have two consecutive nodes with value 4

Step 3: Bypass the Next Node Execute: node.next = node.next.next

2 -> 4 ------> 3
     ^         
   (node)      
  • We update the current node's next pointer to skip over the original 4 node
  • The current node now points directly to the node with value 3
  • The original node with value 4 is no longer part of the list

Final Result: The linked list is now 2 -> 4 -> 3. The value 7 has been successfully removed from the list, and the list has one fewer node. From an external observer's perspective, the node with value 7 has been deleted, even though we technically transformed it into a copy of its successor and removed the successor instead.

Solution Implementation

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, x):
4#         self.val = x
5#         self.next = None
6
7class Solution:
8    def deleteNode(self, node: ListNode) -> None:
9        """
10        Delete a node from a linked list given only access to that node.
11      
12        Since we don't have access to the previous node, we cannot actually remove
13        the current node. Instead, we copy the value of the next node to the current
14        node and then skip the next node by updating the pointer.
15      
16        Args:
17            node: The node to be deleted from the linked list
18          
19        Returns:
20            None (modifies the linked list in-place)
21        """
22        # Copy the value of the next node to the current node
23        # This effectively makes the current node a duplicate of the next node
24        node.val = node.next.val
25      
26        # Skip the next node by updating the pointer
27        # This removes the original next node from the linked list
28        node.next = node.next.next
29
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode(int x) { val = x; }
7 * }
8 */
9class Solution {
10    /**
11     * Deletes a node from a linked list given only access to that node.
12     * This method works by copying the value of the next node to the current node,
13     * then bypassing the next node by updating the pointer.
14     * 
15     * @param node The node to be deleted (not the tail node)
16     */
17    public void deleteNode(ListNode node) {
18        // Copy the value of the next node to the current node
19        node.val = node.next.val;
20      
21        // Bypass the next node by updating the current node's next pointer
22        // This effectively removes the next node from the list
23        node.next = node.next.next;
24    }
25}
26
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9class Solution {
10public:
11    /**
12     * Delete a given node from a linked list (except the tail).
13     * We don't have access to the head of the list, only the node to be deleted.
14     * 
15     * @param node - The node to be deleted from the linked list
16     * 
17     * Algorithm:
18     * Since we cannot access the previous node, we cannot update its next pointer.
19     * Instead, we copy the value of the next node to the current node,
20     * then bypass the next node by updating pointers.
21     */
22    void deleteNode(ListNode* node) {
23        // Copy the value of the next node to the current node
24        // This effectively replaces the current node's data with the next node's data
25        node->val = node->next->val;
26      
27        // Skip the next node by updating the pointer
28        // The next node is now unreachable and will be garbage collected
29        node->next = node->next->next;
30    }
31};
32
1/**
2 * Definition for singly-linked list node.
3 * Each node contains a value and a reference to the next node.
4 */
5class ListNode {
6    val: number;
7    next: ListNode | null;
8  
9    constructor(val?: number, next?: ListNode | null) {
10        this.val = (val === undefined ? 0 : val);
11        this.next = (next === undefined ? null : next);
12    }
13}
14
15/**
16 * Deletes the given node from a linked list.
17 * 
18 * This function deletes a node from a singly-linked list given only access to that node.
19 * The trick is to copy the value from the next node to the current node,
20 * then bypass the next node by updating the pointer.
21 * 
22 * @param node - The node to be deleted from the linked list
23 * @returns void - Modifies the linked list in-place
24 * 
25 * Time Complexity: O(1)
26 * Space Complexity: O(1)
27 */
28function deleteNode(node: ListNode | null): void {
29    // Copy the value from the next node to the current node
30    node.val = node.next.val;
31  
32    // Bypass the next node by updating the pointer to skip it
33    node.next = node.next.next;
34}
35

Time and Space Complexity

Time Complexity: O(1)

The algorithm performs only two constant-time operations:

  1. Copying the value from the next node to the current node: node.val = node.next.val
  2. Updating the pointer to skip the next node: node.next = node.next.next

Both operations take constant time regardless of the size of the linked list, resulting in O(1) time complexity.

Space Complexity: O(1)

The algorithm uses no additional data structures or variables that scale with input size. It only modifies the existing node's value and pointer in-place, requiring constant extra space. Therefore, the space complexity is O(1).

Common Pitfalls

1. Attempting to Delete the Last Node

The most critical pitfall is trying to use this technique when the given node is the last node in the list. Since node.next would be None, attempting to access node.next.val or node.next.next will result in an AttributeError.

Why this happens: The algorithm fundamentally relies on copying data from the next node. When there is no next node, this approach simply cannot work.

Solution: Always validate that the node is not the last node before applying this technique. In interview settings, clarify this constraint. In production code, add a check:

def deleteNode(self, node: ListNode) -> None:
    if node.next is None:
        # Cannot delete the last node with this approach
        raise ValueError("Cannot delete the last node using this method")
  
    node.val = node.next.val
    node.next = node.next.next

2. Misunderstanding the Node Reference Behavior

Some developers mistakenly try to set node = node.next or node = None, thinking this will delete the node. This only changes the local reference and doesn't affect the actual linked list structure.

Why this happens: Confusion between modifying the node object itself versus modifying the local variable reference.

Solution: Remember that you need to modify the properties of the node object (node.val and node.next), not the reference itself:

# Wrong - only changes local reference
node = node.next  # This doesn't modify the linked list

# Correct - modifies the actual node object
node.val = node.next.val
node.next = node.next.next

3. Memory Leak Concerns

While the original next node becomes unreachable after the operation, in languages without automatic garbage collection, this could potentially cause a memory leak. The "deleted" node still exists in memory but is no longer referenced.

Why this happens: The node isn't truly deleted; it's just disconnected from the list.

Solution: In languages like Python, Java, or JavaScript, garbage collection handles this automatically. In C or C++, you might need to explicitly free the memory:

// C++ example
ListNode* temp = node->next;
node->val = node->next->val;
node->next = node->next->next;
delete temp;  // Explicitly free the memory

4. Assuming Value Uniqueness When It's Not Guaranteed

If the linked list can contain duplicate values, this method still works correctly, but developers might incorrectly assume they're deleting a specific instance when they're actually just removing one occurrence.

Why this happens: The problem statement mentions unique values, but this might not always be the case in variations of the problem.

Solution: Be clear about what's being deleted - it's the node at a specific position, not necessarily all nodes with that value. The algorithm works regardless of value uniqueness.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More