Delete a Node Given Only Its Pointer

Problem Given a pointer/reference to a node inside a singly linked list — with no access to the head, and with a guarantee that the node is not the tail — delete that node from the list.

Input / Output

• Input: a reference to the node to delete.
• Output: nothing returned; the list must be mutated in place so the node no longer appears.

Constraints

• No access to the head, so the list cannot be traversed from the front to find the predecessor.
• The target node is guaranteed not to be the last node.
• O(1) time expected.

Example

• List 1 -> 2 -> 3 -> 4, given the pointer to the node holding 3. Afterwards the list must read 1 -> 2 -> 4.
• Tricky case: if the node were the tail, the trick fails — there is no successor to copy from, and you cannot reach the predecessor to null out its next. This is precisely why the problem excludes the tail.