Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Delete Node in a Linked List

MEDIUMProblemSolveExternal Links

Description

You are given a singly-linked list and a reference to a specific node in that list. Your task is to delete that node from the list.

Here's the catch: you are not given access to the head of the linked list. You only receive the node that should be deleted.

By "deleting" the node, we mean:

  • The value of the given node should no longer exist in the linked list.
  • The number of nodes in the list should decrease by one.
  • All values before the given node should remain in their original order.
  • All values after the given node should remain in their original order.

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

Examples

Example 1

Input: head = [4, 5, 1, 9], node = 5

Output: [4, 1, 9]

Explanation: We are given a pointer to the node with value 5. After deletion, the linked list becomes 4 → 1 → 9. The node with value 5 no longer exists in the list, and the remaining nodes maintain their original order.

Example 2

Input: head = [4, 5, 1, 9], node = 1

Output: [4, 5, 9]

Explanation: We are given a pointer to the node with value 1. After deletion, the linked list becomes 4 → 5 → 9. The node with value 1 is removed while all other nodes remain in their original order.

Example 3

Input: head = [1, 2, 3, 4], node = 3

Output: [1, 2, 4]

Explanation: We are given a pointer to the node with value 3. After deletion, the linked list becomes 1 → 2 → 4. Notice that even though we never had access to the head node (1), the list is correctly modified.

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

Editorial

Brute Force

Intuition

The typical way to delete a node from a singly linked list is to find the previous node and set its next pointer to skip over the target node. This requires traversing from the head of the list until we find the node just before the one we want to delete.

Imagine a chain of paperclips. To remove one from the middle, you would normally go back to the paperclip before it, unhook it, and re-hook it to the paperclip after the removed one. This requires access to the starting end of the chain.

However, in this problem, we do not have access to the head node. We only have a pointer directly to the node we need to delete. So the standard traversal approach is simply not possible here. We cannot find the previous node because we cannot traverse backwards in a singly linked list, and we cannot start from the head because we don't have it.

This means the brute force approach of 'find the previous node and re-link' is fundamentally blocked by the constraint of this problem.

Step-by-Step Explanation

Let's think through why the standard deletion approach fails:

Setup: head = [4, 5, 1, 9], node = 5 (we receive a pointer to the node with value 5).

Step 1: In a normal deletion, we would start at the head node (value 4) and traverse forward.

Step 2: We would find that node with value 4 has its next pointing to our target node (value 5).

Step 3: We would set node_4.next = node_5.next, effectively skipping over node 5.

Step 4: The list would become 4 → 1 → 9.

The Problem: Step 1 and Step 2 are impossible because we don't have access to the head node. We receive only a pointer to the node with value 5. From that node, we can only go forward (to 1, then 9), never backward (to 4).

Since a singly linked list has no backward pointers, there is no way to reach the previous node (value 4) from the given node (value 5). The standard approach is blocked.

Algorithm

Standard deletion (requires head access):

  1. Start at the head of the linked list
  2. Traverse until finding the node whose next points to the target node
  3. Set previous.next = target.next to bypass the target
  4. Delete/free the target node

This approach is NOT applicable to our problem because we lack access to the head.

Code

// Standard deletion — requires head access (NOT applicable here)
// Shown for learning purposes only
void deleteNode(ListNode* head, ListNode* target) {
    // If head itself is the target
    if (head == target) {
        head = head->next;
        return;
    }
    
    // Traverse to find previous node
    ListNode* prev = head;
    while (prev->next != nullptr && prev->next != target) {
        prev = prev->next;
    }
    
    // Bypass the target
    if (prev->next == target) {
        prev->next = target->next;
    }
}
# Standard deletion — requires head access (NOT applicable here)
# Shown for learning purposes only
def delete_node(head, target):
    # If head itself is the target
    if head == target:
        head = head.next
        return head
    
    # Traverse to find previous node
    prev = head
    while prev.next is not None and prev.next != target:
        prev = prev.next
    
    # Bypass the target
    if prev.next == target:
        prev.next = target.next
    
    return head
// Standard deletion — requires head access (NOT applicable here)
// Shown for learning purposes only
public void deleteNode(ListNode head, ListNode target) {
    // If head itself is the target
    if (head == target) {
        head = head.next;
        return;
    }
    
    // Traverse to find previous node
    ListNode prev = head;
    while (prev.next != null && prev.next != target) {
        prev = prev.next;
    }
    
    // Bypass the target
    if (prev.next == target) {
        prev.next = target.next;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the standard approach, we traverse from the head to find the predecessor of the target node. In the worst case, the target is near the end, requiring us to visit all n nodes.

Space Complexity: O(1)

Only a single pointer variable (prev) is used regardless of list size.

Limitation: This approach requires head access, which we do not have in this problem.

Why This Approach Is Not Efficient

The standard deletion approach isn't just inefficient — it's impossible in this problem. We simply don't have a pointer to the head of the list, so we cannot traverse backward to find the previous node.

But this limitation leads to a brilliant insight: what if we don't need to remove the node at all? Instead of physically removing the given node from the chain, what if we make it impersonate the next node?

The idea is: copy the data from the next node into the current node, and then delete the next node instead. From the outside, it looks exactly as if the given node was deleted — the value disappears, the list shrinks by one, and the order is preserved. This is like a spy taking on a new identity: instead of extracting the spy, you change who the spy pretends to be.

Optimal Approach - Copy and Skip

Intuition

Since we cannot reach the previous node, we use a clever trick: instead of removing the given node, we overwrite it with the next node's data and then remove the next node.

Think of it like a relay race. If runner #3 needs to be removed from the team but you can only communicate with runners #3, #4, and beyond (not runners #1 and #2), you tell runner #3 to take on runner #4's number and baton, and then runner #4 quietly leaves. To the audience, it looks like runner #3 disappeared — but actually, runner #3 is now playing the role of runner #4.

Concretely:

  1. Copy node.next.val into node.val — the current node now holds the next node's value.
  2. Set node.next = node.next.next — the current node now points past the next node, effectively removing the next node from the chain.

The result: the value that was in the given node is gone from the list, the list is one node shorter, and all other values remain in order. This satisfies every requirement of the problem.

Step-by-Step Explanation

Let's trace through with head = [4, 5, 1, 9], node = 5:

Step 1: We receive a pointer to the node with value 5. The list looks like:
4 → [5] → 1 → 9 → null
The brackets indicate the node we have a pointer to.

Step 2: Look at the next node's value: node.next.val = 1.

Step 3: Copy the next node's value into the current node: node.val = 1.
Now the list looks like: 4 → [1] → 1 → 9 → null.
Notice there are temporarily two nodes with value 1.

Step 4: Save a reference to node.next (the original node with value 1).

Step 5: Bypass the next node: node.next = node.next.next.
The current node now points to the node with value 9.
The list becomes: 4 → [1] → 9 → null.

Step 6: The original next node (which had value 1) is now disconnected and can be garbage collected.

Result: The list is 4 → 1 → 9. The value 5 no longer exists. The list shrank by one node. All done in O(1) time!

Copy-and-Skip Deletion — Impersonate the Next Node — Watch how the given node copies the next node's value, then skips over the next node. The effect is the same as if the given node was removed.

Algorithm

  1. Copy the value of node.next into node:
    • node.val = node.next.val
  2. Skip over the next node by updating the pointer:
    • node.next = node.next.next
  3. The next node is now orphaned and will be garbage collected

That's it — just two lines of code. The simplicity is the beauty of this approach.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        // Copy the next node's value into the current node
        node->val = node->next->val;
        
        // Skip the next node
        node->next = node->next->next;
    }
};
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # Copy the next node's value into the current node
        node.val = node.next.val
        
        # Skip the next node
        node.next = node.next.next
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        // Copy the next node's value into the current node
        node.val = node.next.val;
        
        // Skip the next node
        node.next = node.next.next;
    }
}

Complexity Analysis

Time Complexity: O(1)

We perform exactly two operations — one value copy and one pointer reassignment. No traversal, no loops, no searching. Constant time regardless of list size.

Space Complexity: O(1)

No extra data structures are used. We only modify existing pointers and values in place.

This is optimal in both time and space. The O(1) time is a dramatic improvement over the O(n) traversal approach, made possible by the creative insight of copying data instead of rearranging the structure.

Caveats worth noting:

  • This approach does NOT work if the node to be deleted is the last node (tail), because there is no next node to copy from. The problem guarantees the node is not the tail.
  • This approach modifies the value of the given node, not just pointers. If external code holds a reference to the node and expects its value to remain the same, this could cause issues. For this LeetCode problem, that is acceptable.