DSA problem
Delete Node in a Linked List
There is a singly linked list and you are given a reference to a node inside it, but NOT the head of the list. The task is to delete the given node from the list. It is guaranteed that the node to be deleted is not the tail node.
This problem is a clever twist on linked-list deletion. Normally to delete a node you need access to its predecessor, so you can reroute prev.next to skip the doomed node. Here you have no head and no way to reach the predecessor, so that classic strategy is impossible.
The key realization is that you do not actually have to remove the physical node you were given; you only have to make the list behave as if its value were gone. Since you have access to the node's successor, you can copy the successor's value into the current node, and then splice out the successor instead.
The optimal approach is therefore a constant-time trick: set node.val to node.next.val, then set node.next to node.next.next. This effectively shifts every subsequent value one step earlier and drops one node, producing a list identical to one with the target value removed. It runs in O(1) time and O(1) space.
Examples
head = [4,5,1,9], node = 5[4,1,9]head = [4,5,1,9], node = 1[4,5,9]head = [1,2,3,4], node = 3[1,2,4]Constraints
- The number of nodes in the given 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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.