[LeetCode] 237. Delete Node in a Linked List

Problem

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.

BCR(Best Conceivable Runtime)

To delete the given node, it only needs $O(1)$ because we only have to do connect the previous of the node and the next of the node.

Solution

The first thing came to mind was "Is this problem can be solved?". If we want to delete some node, we need to have a delete node, and the previous of one. So it can be deleted by connecting nodes between the previous and the next. But the problem doesn't give us head, so we can't access the previous one. Only we can do is access node what we want to delete. We can access node and node.next. So, basic idea is just copy the node.next to node because there is already a connection between the previous and node.

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