237. Delete Node in a Linked List

Description

Given a node in a singly-linked list, delete the node from the list. The node to be deleted is not necessarily the last node. The list is represented as a series of nodes where each node contains a value and a pointer to the next node. The function should modify the linked list directly to remove the specified node.

Intuition

Since we are not given access to the head of the list, the only way to delete a node is to copy the value from the next node into the current node and then remove the next node. This effectively "shifts" the data of the next node into the current node and removes the next node from the list. This approach works because we are guaranteed that the node to be deleted is not the last node.

Approach

1. Copy Value: - Copy the value of the next node into the current node. This step effectively changes the value of the current node to match the node that should be deleted.
2. Move to Next Node: - Update the current node to be the next node in the list. This prepares the node for the next iteration.
3. Remove the Last Node: - When reaching the second-to-last node, copy the value of the last node into it and set its next pointer to null. This effectively removes the last node from the list.
4. Edge Cases: - The function assumes that the node to be deleted is not the last node. If the last node needs to be removed, additional handling would be required.

Example

Consider the linked list: 4 -> 5 -> 1 -> 9 and we need to delete node 5.

• After copying the value of node 1 into node 5, the list becomes: 4 -> 1 -> 1 -> 9.
• Finally, set the next pointer of node 1 (formerly 5) to null, resulting in: 4 -> 1 -> 9.

Complexity

Time Complexity:

O(1). The deletion operation involves a fixed number of steps: copying a value and updating pointers. It does not depend on the length of the list.

Space Complexity:

O(1). The algorithm uses a constant amount of extra space regardless of the size of the linked list.

Code

C++

class Solution {
public:
    void deleteNode(ListNode* node) {
        while (node->next && node->next->next) {
            node->val = node->next->val;
            node = node->next;
        }
        node->val = node->next->val;
        node->next = nullptr;
    }
};

Python

class Solution:
    def deleteNode(self, node: ListNode) -> None:
        while node.next and node.next.next:
            node.val = node.next.val
            node = node.next
        node.val = node.next.val
        node.next = None

Java

class Solution {
    public void deleteNode(ListNode node) {
        while (node.next != null && node.next.next != null) {
            node.val = node.next.val;
            node = node.next;
        }
        node.val = node.next.val;
        node.next = null;
    }
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

var deleteNode = function(node) {
    // console.log(node.next)
    
    while (node.next && node.next.next) {
        node.val = node.next.val;
        node = node.next;
    }

    node.val = node.next.val;
    node.next = null;
    return;
    
};