Delete Node in a Linked List

medium linked list

Problem

You are given a node (not the tail) of a singly linked list. Delete that node from the list. You don't have access to the head — only the node you must delete.

Inputhead = [4,5,1,9], node = 5

Output[4,1,9]

Copy 1 into the 5-node, then point past the original 1 node.

list (comma-separated)

delete value

def delete_node(node):
    node.val = node.next.val
    node.next = node.next.next

function deleteNode(node) {
  node.val = node.next.val;
  node.next = node.next.next;
}

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

void deleteNode(ListNode* node) {
    node->val = node->next->val;
    node->next = node->next->next;
}

Explanation

The twist here is that you are not given the head of the list — you only get a pointer to the node you must delete. Normally to delete a node you find the node before it and skip over it, but here you can't walk backward to reach that earlier node.

The clever idea is to not actually delete the given node at all. Instead, we copy the next node's value into the current node, then unlink the next node. The end result looks exactly as if the current node had been removed.

In code, node.val = node.next.val overwrites this node's value with its neighbor's value. Then node.next = node.next.next skips past that neighbor, so the duplicate copy disappears from the list.

Example: list is 4 → 5 → 1 → 9 and we are handed the 5 node. We copy 1 into it, giving 4 → 1 → 1 → 9, then point past the original 1 node to get 4 → 1 → 9.

This only works because the node is not the tail — there must be a next node to copy from. It runs in constant time since we just touch one node.

Time: O(1) Space: O(1)