237. Delete Node in a Linked List
Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 0
Acceptance rate: 67.4%
Problem Breakdown
The problem requires deleting a node from a singly-linked list when only the node itself is given, not the head of the list. The node to be deleted is guaranteed not to be the tail node.
Inputs:
- A node in a singly-linked list that needs to be deleted.
- The node is not the tail node.
Outputs:
- The linked list with the specified node removed.
Implicit Constraints or Tricky Edge Cases:
- The node to be deleted is guaranteed not to be the tail node, so we don’t need to handle cases where the next node is null.
- The linked list has at least two nodes since the node to be deleted cannot be the tail.
Intuition
The brute-force approach would involve traversing the list from the head to find the node just before the one to be deleted and then updating its next pointer. However, this requires access to the head of the list, which is not provided in this problem.
A key insight is that since we have direct access to the node to be deleted, we can copy the value of the next node into the current node and then delete the next node instead. This effectively removes the current node from the list without needing to traverse it.
Approach
- Copy the value of the next node into the current node.
- Update the
nextpointer of the current node to skip the next node, thus removing it from the list.
This approach leverages the fact that we have direct access to the node to be deleted and can manipulate its neighbors directly.
Complexity Analysis
- Time Complexity: O(1) - The operation involves a constant number of steps regardless of the size of the linked list.
- Space Complexity: O(1) - No additional space is required beyond a few variables for pointers.
Solution
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def deleteNode(node):
# Copy the value of the next node to the current node
node.val = node.next.val
# Update the next pointer to skip the next node
node.next = node.next.next
Edge Cases Handled
- The node to be deleted is not the tail node, so there is always a valid
nextnode. - The linked list has at least two nodes, ensuring that the operation can proceed without errors.