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.

Supposed the linked list is1 -> 2 -> 3 -> 4and you are given the third node with value3, the linked list should become1 -> 2 -> 4after calling your function.

Brainstorm

The catch here is that we only have access to the node to delete. This requires a different approach compared to when we have access the node before the one to delete (in which case we would have the previous node skip over the node to delete and connect to the one after).

However, there's nothing requiring us to have to delete an actual node in a memory address itself! Rather, we can simply copy the next node's data over to the node to delete, and just overwrite the old data, thus achieving the same effect as deleting a node.

Approach #1: Copy Over the Next Node's Val and Next

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

Time complexity: $$O(1)$$

Space complexity: $$O(1)$$