Problem of The Day: Delete Node in a Linked List

Problem Statement

Intuition

The intuition here appears to be to delete the given node by modifying its value and next pointer to mimic the effect of deleting it.

Approach

Since we are not given head node in the singly-linked list. We need to do the following procedure:

• The function takes in a node as input, which is the node to be deleted.
• It first assigns the current node to curr.
• Then it assigns the next node of curr to next_node.
• It updates the next pointer of curr to point to the node after next_node.
• Finally, it updates the value of curr to the value of next_node, effectively mimicking the deletion of next_node.

Complexity

• Time complexity: O(1)

• Space complexity: O(1)

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        curr = node
        next_node = curr.next
        curr.next = next_node.next
        curr.val = next_node.val

Editorial Solution

class Solution:
    def deleteNode(self, node):
        # Overwrite data of next node on current node.
        node.val = node.next.val
        # Make current node point to next of next node.
        node.next = node.next.next