237.md

237. Delete Node in a Linked List

Description

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Suppose the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Thinking Process

1. Since only the node-to-delete is given, we have to delete it by value (since we don't have access to the node before it)
2. Duplicate the value of node.next to node, then delete node.next by linking node directly to node.next.next

Code

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

Complexity

1. Space complexity is O(1)
2. Time complexity is O(1) since it only requires 2 operations