Delete Node in a Linked List solution and explanation
Google
9 more videos on this problem
Delete Node in a Linked List | Can you solve it ?take U forward · 3:44 · 132K views
Delete Node in a Linked List | Super Easy | Apple | Microsoft | Leetcode 237codestorywithMIK · 12:01 · 54K views
LeetCode 237. Delete Node in a Linked List Solution Explained - JavaNick White · 2:51 · 30K views
Delete Node in a Linked List | Leetcode #237Techdose · 3:22 · 29K views
Delete Node in a Linked List | LeetCode 237 | Coding Interview TutorialTerrible Whiteboard · 7:24 · 5K views
LEETCODE 237 (JAVASCRIPT) | DELETE A NODE IN A LINKED LISTAndy Gala · 5:14 · 3K views
237. Delete Node in a Linked List | Singly Linked List | Easy |Aryan Mittal · 7:34 · 3K views
LeetCode 237: Delete Node in a Linked List - Interview Prep Ep 57Fisher Coder · 10:14 · 3K views
Delete Node in a Linked List - LeetCode 237 - Python #leetcode #linkedlistDeepti Talesra · 6:57 · 2K views
Delete Node in a Linked List (LeetCode 237) (How to Think out of the Box)CodeWithARB · 10:17 · 1K views
The problem
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:
- The value of the given node should not exist in the linked list.
- The number of nodes in the linked list should decrease by one.
- All the values before
nodeshould be in the same order. - All the values after
nodeshould be in the same order.
Custom testing:
- For the input, you should provide the entire linked list
headand the node to be givennode.nodeshould not be the last node of the list and should be an actual node in the list. - We will build the linked list and pass the node to your function.
- The output will be the entire list after calling your function.
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:
- The number of the 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
nodeto be deleted is in the list and is not a tail node.
Approach overview
Problem Overview: You’re given a reference to a node inside a singly linked list, not the head. The task is to delete that node from the list while keeping the rest of the list intact. The constraint is the key challenge: without access to the previous node, you can’t perform the usual pointer update.
Approach 1: Copy and Bypass (O(1) time, O(1) space)
This trick avoids needing the previous node. Copy the value from the next node into the current node using node.val = node.next.val. Then bypass the next node by updating the pointer: node.next = node.next.next. The original "next" node effectively disappears from the list. This works because the node to delete is guaranteed not to be the tail, so node.next always exists. The structure of the linked list remains valid and the deletion appears as if the original node was removed.
Approach 2: Utilize Two Pointers (O(n) time, O(1) space)
If the head of the list is available, you can traverse the list to locate the previous node. Use two pointers: one iterating through the list and another tracking the previous node. When the current pointer matches the node that needs deletion, update prev.next = curr.next to unlink it. This is the standard deletion method in a singly linked list. The traversal introduces linear time complexity, similar to many two pointer scanning patterns where one pointer follows another through the structure.
Recommended for interviews: The expected solution is the Copy and Bypass approach. Interviewers want to see whether you recognize the constraint that the previous node is unavailable. Copying the next node’s value and skipping it demonstrates a deep understanding of pointer manipulation in linked lists. The traversal approach shows baseline knowledge, but the O(1) trick is the real signal of problem-solving skill.
Approach 1: Copy and Bypass
This approach leverages the fact that we have access to the node to be deleted and that deletion does not mean removing from memory but rather bypassing this node.
By copying the value from the next node to the node to be deleted and rearranging the pointers, we can effectively 'delete' the node without needing access to the head of the list.
def deleteNode(node):
if not node or not node.next:
return
node.val = node.next.val
node.next = node.next.nextpublic void deleteNode(ListNode node) {
if (node == null || node.next == null) return;
ListNode nextNode = node.next;
node.val = nextNode.val;
node.next = nextNode.next;
}void deleteNode(ListNode* node) {
if (node == nullptr || node->next == nullptr) return;
ListNode* nextNode = node->next;
node->val = nextNode->val;
node->next = nextNode->next;
delete nextNode;
}function deleteNode(node) {
if (!node || !node.next) return;
node.val = node.next.val;
node.next = node.next.next;
}void deleteNode(struct ListNode* node) {
if (node == NULL || node->next == NULL) return;
struct ListNode* nextNode = node->next;
node->val = nextNode->val;
node->next = nextNode->next;
free(nextNode);
}public void DeleteNode(ListNode node) {
if (node == null || node.next == null) return;
node.val = node.next.val;
node.next = node.next.next;
}Python solution is straightforward; we reassign the value and pointer, with no need for explicit memory management.
Time Complexity: O(1), changes are instantaneous and isolated.
Space Complexity: O(1), no additional storage is required.
Approach 2: Node assignment
We can replace the value of the current node with the value of the next node, and then delete the next node. This can achieve the purpose of deleting the current node.
Time complexity O(1), space complexity O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
/**
Do not return anything, modify it in-place instead.
*/
function deleteNode(node: ListNode | null): void {
node.val = node.next.val;
node.next = node.next.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteNode(node *ListNode) {
node.Val = node.Next.Val
node.Next = node.Next.Next
}Complexity comparison
| Approach | Complexity |
|---|---|
| Copy and Bypass | Time Complexity: O(1), changes are instantaneous and isolated. Space Complexity: O(1), no additional storage is required. |
| Node assignment | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Copy and Bypass | O(1) | O(1) | When only the target node is given and it is guaranteed not to be the tail |
| Two Pointers Traversal | O(n) | O(1) | When the head pointer is available and you want the standard deletion logic |
Frequently asked questions
Is Delete Node in a Linked List easy or hard?
Delete Node in a Linked List is labeled Medium on LeetCode, but many developers find it tricky because the node to delete is given without the head. Recognizing the copy-and-bypass trick is the key insight.
Delete Node in a Linked List Python/Java solution
In Python or Java, the implementation is identical in logic: copy the next node's value and update the pointer to skip it. This constant-time solution modifies the current node rather than physically removing it from memory.
How to solve Delete Node in a Linked List in O(1)?
Use the copy-and-bypass trick. Assign the next node's value to the current node using node.val = node.next.val, then update node.next = node.next.next. This effectively removes the next node while making the current node appear deleted.
What is the best approach for Delete Node in a Linked List?
The optimal approach is the Copy and Bypass technique with O(1) time and O(1) space complexity. Copy the value from the next node into the given node, then update the next pointer to skip the next node. This works because the node to delete is guaranteed not to be the tail.
Is Delete Node in a Linked List asked at Google/Amazon/Meta?
Delete Node in a Linked List is a classic pointer manipulation problem frequently asked in technical interviews at companies like Google, Amazon, and Meta. It tests understanding of linked list structure and edge cases involving node references.
What data structure is used in Delete Node in a Linked List?
The problem uses a singly linked list. Each node contains a value and a pointer to the next node. The challenge revolves around pointer manipulation without access to the previous node in the list.
What is the time complexity of Delete Node in a Linked List?
The optimal solution runs in O(1) time because it performs constant operations: copying a value and updating a pointer. A traditional traversal approach would take O(n) time since you must iterate through the linked list to find the previous node.