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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete Node in a Linked List

Difficulty: Medium

Problem Description

Given a singly-linked list and a node to be deleted, delete that node without access to the head of the list. The node to be deleted is guaranteed to be not the last node in the list.

Key Insights

  • The node to be deleted is not the last node, which simplifies the deletion process.
  • We can copy the value of the next node into the current node and then delete the next node.
  • This approach effectively removes the target node from the linked list without needing to traverse from the head.

Space and Time Complexity

Time Complexity: O(1) - The operation is done in constant time since we only modify the current node and its next node. Space Complexity: O(1) - No additional space is used apart from the pointers.

Solution

To delete a node in a linked list when given only that node, we can utilize the fact that we can modify the current node's value and its next pointer. The algorithm involves:

  1. Copying the value of the next node to the current node.
  2. Changing the current node's next pointer to skip the next node.
  3. Effectively, this removes the current node from the linked list.

This approach directly modifies the linked list without needing to traverse from the head.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteNode(node: ListNode) -> None:
    # Copy the value from the next node to the current node
    node.val = node.next.val
    # Skip the next node
    node.next = node.next.next
← Back to All Questions