Watch 10 video solutions for Delete Node in a Linked List, a medium level problem involving Linked List. This walkthrough by NeetCode has 224,471 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a singly-linked list head and we want to delete a node node in it.
You are given the node to be deleted node. You will not be given access to the first node of head.
All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.
Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:
node should be in the same order.node should be in the same order.Custom testing:
head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
Example 1:
Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Example 2:
Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
Constraints:
[2, 1000].-1000 <= Node.val <= 1000node to be deleted is in the list and is not a tail node.Problem Overview: You are given a node in the middle of a singly linked list and must delete it. The head of the list is not provided, so you cannot traverse from the start to locate the previous node.
Approach 1: Copy and Bypass (O(1) time, O(1) space)
This approach avoids searching for the previous node entirely. Copy the value from the next node into the current node, then bypass the next node by updating node.next = node.next.next. The original next node effectively disappears from the list, which simulates deleting the given node. The key insight is that you cannot remove the current node without access to its predecessor, so you overwrite its value and remove the node after it instead. This technique is common in linked list problems where only a reference to the target node is available.
Approach 2: Utilize Two Pointers (O(n) time, O(1) space)
If the list head is available, you can traverse the list to locate the node immediately before the target node. Use two pointers: one pointer tracks the current node while another trails behind to maintain the previous reference. Once the target node is found, update the previous node's next pointer to skip it. This is the traditional deletion method used in singly linked lists. It relies on sequential traversal and pointer updates, a common pattern when working with two pointers or iterative traversal in linked list structures.
Recommended for interviews: Interviewers expect the Copy and Bypass trick because the problem explicitly removes access to the head node. Recognizing that you can overwrite the node’s value demonstrates strong understanding of pointer manipulation and linked list behavior. Mentioning the standard traversal deletion shows foundational knowledge, but the O(1) overwrite method is the intended solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Copy and Bypass | O(1) | O(1) | When only the node reference is given and the previous node is unknown |
| Two Pointers Traversal | O(n) | O(1) | When the head of the linked list is available and standard deletion is required |