Delete Node in a Linked List
Understanding the Problem
This looks like a standard linked list deletion problem, with one restriction that changes everything: you are not given the head of the list. You only have a reference to the node you need to delete.
In a typical singly-linked list deletion, you traverse from the head, find the node immediately before the target, and rewire previous.next to skip the target node. But here, you cannot reach the previous node. Singly-linked lists only have forward pointers, so there is no way to go backward from the given node.
The question becomes: how do you remove a node when you can only see forward from it? Instead of unlinking the node from the chain, you make it take over the next node's value and links, then remove the next node instead. The net effect is the same.
Key Constraints:
2 <= number of nodes <= 1000→ The list always has at least two nodes. The node to delete always has a predecessor somewhere, even though we cannot access it.node is not the tail→ The node we need to delete is guaranteed to have a next node. Both approaches below copy from the next node, so this guarantee is what makes them possible.All values are unique→ Each value identifies one node, so the expected output is unambiguous.
Approach 1: Shift Values Forward
Intuition
We cannot do the traditional pointer rewire without the previous node, but we can still look forward. One option is to shift every value one position toward the front, starting at the given node: the target takes the next node's value, that node takes the value after it, and so on until the tail becomes redundant and can be dropped.
The list behaves like a line of people holding numbered signs. If person #3 needs to "leave," everyone behind #3 passes their sign forward. Person #3 takes #4's sign, #4 takes #5's sign, and so on. The last person has no sign to receive, so they step out. The result looks the same as if person #3 left.
The cost is a full pass over every node between the target and the tail.
Algorithm
- Starting from the given node, copy the next node's value into the current node.
- Move to the next node and repeat.
- When you reach the second-to-last node (its next is the tail), copy the tail's value into it, then set its next to null to remove the tail.
Visualization and Code
Loading animation...
- Time Complexity: O(n). In the worst case, the node to delete is right after the head, so we shift values through almost the entire list.
- Space Complexity: O(1). We use a single pointer variable and no extra data structures.
Shifting every value to the tail does more work than the problem requires. The next approach removes the value by touching only the given node and its immediate neighbor.
Approach 2: Copy and Skip (Optimal)
Intuition
Only one value needs to disappear, so shifting the entire suffix is unnecessary. Copy the next node's value into the current node, then unlink the next node. The given node now carries its successor's value, and the successor is gone from the chain.
In the line-of-people analogy: instead of everyone passing signs forward, you copy the sign of the person behind you, and that person steps out. To anyone looking at the line from the front, it is as if you left. The list shrinks by one and the right value is gone, in two constant-time operations.
From the list's perspective, a node is defined by its value and its position in the chain, not by which memory location holds it. After the copy and the unlink, the location that every predecessor points to holds the successor's value, and it links to everything after the successor through node.next.next. The node physically removed from the chain is node.next, but the value that disappears from the list is the original node.val, which is what the problem asks for: the value is gone and the list is one node shorter, with all other values in their original order.
Algorithm
- Copy the value of the next node into the current node:
node.val = node.next.val. - Update the current node's next pointer to skip the next node:
node.next = node.next.next.
Visualization and Code
Loading animation...
- Time Complexity: O(1). We perform two operations regardless of the list size: one value copy and one pointer update. There is no loop and no traversal.
- Space Complexity: O(1). We modify existing node fields and allocate nothing.