237. Delete Node in a Linked List

Intuition

Since we don't have access to the head of the list, and we’re told the node to be deleted is not the last one, the only way to "delete" the node is to copy the value from the next node into the current node, and then skip the next node.

Effectively, we're replacing the current node with the next node and removing the next node instead.

Complexity

Space Complexity
Time Complexity

O(1)\text{O}(1)

O(N)\text{O}(N)

Code

public void deleteNode(ListNode nodeToDelete) {
    // 'currentNode' is the node we want to delete
    // 'nextNode' is the node right after 'currentNode'
    ListNode currentNode = nodeToDelete;
    ListNode nextNode = nodeToDelete.next;

    // Shift all the values left by copying next node's value to current
    while (nextNode.next != null) {
        currentNode.val = nextNode.val;
        currentNode = nextNode;
        nextNode = nextNode.next;
    }

    // Copy the value of the last node
    currentNode.val = nextNode.val;
    
    // Remove the last node
    currentNode.next = null;
}

Last updated