237. Delete Node in a Linked List – Leetcode Solutions

Description

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:

• The value of the given node should not exist in the linked list.
• The number of nodes in the linked list should decrease by one.
• All the values before node should be in the same order.
• All the values after node should be in the same order.

Custom testing:

• For the input, you should provide the entire linked list 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.
• We will build the linked list and pass the node to your function.
• The output will be the entire list after calling your function.

Examples:

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.

Solution in Python

Approach:

1. Copy the value of the next node into the current node to be deleted.
2. Set the next pointer of the current node to the next pointer of the next node (effectively skipping the next node).
3. This will “delete” the node in the sense that its value and next pointer have been overwritten by those of the next node, and the next node itself is skipped.

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # Copy the value of the next node into the current node
        node.val = node.next.val
        
        # Bypass the next node by pointing to the next of next node
        node.next = node.next.next

Explanation:

1. Copy the value of the next node:
   • The node to be deleted is node, and its value is replaced with the value of the next node: node.val = node.next.val.
2. Bypass the next node:
   • The next pointer of node is updated to skip the next node: node.next = node.next.next. This effectively removes the next node from the list.

Example:

For the input linked list: 4 -> 5 -> 1 -> 9, if the node to delete is the one with value 5:

• After executing the code, the linked list becomes: 4 -> 1 -> 9. The node with the value 5 is removed.

Solution in Javascript

var deleteNode = function(node) {
    // Step 1: Copy the value of the next node into the current node
    node.val = node.next.val;

    // Step 2: Change the next pointer to skip the next node
    // Now, the current node's next points to the next of next node
    node.next = node.next.next;
};

Solution in Java

class Solution {
    public void deleteNode(ListNode node) {
        // Step 1: Copy the value of the next node into the current node
        node.val = node.next.val;

        // Step 2: Update the next pointer to skip the next node
        // Now, the current node points to the node after the next one
        node.next = node.next.next;
    }
}

Solution in C++

class Solution {
public:
    void deleteNode(ListNode* node) {
        // Step 1: Copy the value of the next node into the current node
        node->val = node->next->val;
        
        // Step 2: Update the current node's next pointer to skip the next node
        // The current node now points to the next of next node
        node->next = node->next->next;
    }
};