Delete Node in a Linked List
Delete Node in a Linked List is a medium linked list problem solved with the miscellaneous pattern.
The best approach, optimal (copy the next node, then skip it), runs in O(1) time and O(1) space.
Problem
You are given only a node inside a singly linked list (not the head), and it is guaranteed not to be the last node. Delete it, meaning its value should no longer appear in the list and the order of the other values is unchanged.
Examples
Example 1
- Input
head = [4, 5, 1, 9], node = 5- Output
[4, 1, 9]
Example 2
- Input
head = [4, 5, 1, 9], node = 1- Output
[4, 5, 9]
Constraints
- You get only the node to delete, not the head.
- The node is never the tail; values are unique.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Optimal (copy the next node, then skip it) | O(1) | O(1) |
1Optimal (copy the next node, then skip it)
O(1)O(1)Copy the next node's value into this node and unlink the next node. The value disappears from the list even though a different physical node is removed. There is no other approach, because the previous node is unreachable.
- 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;
}
}Edge cases to test
- The node is second to last
Hints
Hint 1
You cannot reach the previous node. Can you make this node look like the next one instead?
FAQ
What is the best time complexity for Delete Node in a Linked List?
Optimal (copy the next node, then skip it) runs in O(1) time and O(1) extra space.
Which pattern does Delete Node in a Linked List use?
It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Copy List with Random Pointer, Intersection of Two Linked Lists, Partition List.
Which edge cases should I test for Delete Node in a Linked List?
The node is second to last.