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.In #237 Delete Node in a Linked List, you are given direct access to the node that needs to be removed, but you do not have access to the head of the linked list. This constraint makes the typical deletion approach (tracking the previous node) impossible.
The key insight is to simulate deletion by copying the value from the next node into the current node and then bypassing the next node. In practice, you assign node.val = node.next.val and update the pointer using node.next = node.next.next. This effectively removes the next node while making the current node appear deleted.
This method works because the problem guarantees the node to delete is not the tail. The operation modifies pointers locally and avoids traversing the entire list, making it extremely efficient. The approach achieves constant time and constant space complexity, which is optimal for this scenario.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Copy next node value and bypass next node | O(1) | O(1) |
NeetCode
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.
Time Complexity: O(1) since we're performing constant-time operations.
Space Complexity: O(1) because we aren't using any auxiliary data structures.
1public void deleteNode(ListNode node) {
2 if (node == null || node.next == null) return;
3 ListNode nextNode = node.Java doesn't require manual memory management, so we simply update the node's value and its pointer. Memory reclamation is handled by the garbage collector.
This approach uses two pointers to manage nodes, allowing for a genuine swap and linkage manipulation. It reinforces the conceptual understanding of linked list pointer adjustments.
Note: The fundamentals are the same as we still replace and link to carry out the 'deletion'.
Time Complexity: O(1), never fluctuating beyond direct node handling.
Space Complexity: O(1), not utilizing external structures.
1 if (node == nullptr || node->next == nullptr) return;
ListNode* nextNode = node->next;
node->val = nextNode->val;
node->next = nextNode->next;
delete nextNode;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem are common in technical interviews at companies like Amazon, Meta, and Google. It tests core linked list fundamentals and the ability to reason about constraints in pointer-based data structures.
The optimal approach is to copy the value from the next node into the current node and then bypass the next node. This effectively removes the next node from the list while making the current node appear deleted. It runs in constant time and space.
Traditional linked list deletion requires access to the previous node so that its next pointer can be updated. In this problem, only the node to be deleted is given, so we cannot traverse back to the previous node. Therefore, we modify the current node instead.
This problem primarily tests understanding of singly linked list pointer manipulation. It also evaluates whether candidates can think creatively about modifying node values and references when typical traversal methods are unavailable.
This C++ implementation proceeds similarly to C, with slightly refined type safety and object handling.