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 |
|---|---|
| $\(\text{O}(1)\)$ | $\(\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;
}