We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Node in a Linked List

Number: 237

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Oracle, PayPal, Microsoft, Google, Apple, Meta, Adobe

Problem Description

Given only a reference to a node (that is not the tail) in a singly-linked list, remove that node from the list. Since you do not have access to the head of the list, you must modify the node's value and pointer to effectively delete it.

Key Insights

  • You are given direct access to the node to be deleted, not the head.
  • The node to be deleted is guaranteed not to be the tail.
  • The solution involves copying the next node’s value into the current node.
  • Then, bypass the next node by updating the pointer of the current node to point to the next node’s next pointer.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The key idea is to simulate deletion by copying the next node's data into the current node and then deleting the next node. Since you don't have access to the node before the one to be deleted, you can't adjust its pointer. Instead, you overwrite the target node’s value with the next node’s value and update the pointer to skip the next node. This in-place modification effectively removes the original node value from the list without requiring traversal from the head.

Code Solutions

# Function to delete a node in a linked list.
def deleteNode(node):
    # Copy the next node's value into the current node.
    node.val = node.next.val
    # Bypass the next node by pointing to the next node's next.
    node.next = node.next.next
← Back to All Questions