Delete non-tail Node in linked list, Given only access to that Node

Problem

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Examples

Example 1:

graph LR;
4 --> 5 --> 1 --> 9

style 5 fill:#FF9933
  

5 is given node.

graph LR;
4 ----> 1 --> 9
  

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Solution

Method 1 - Copy the value

To delete a node, we have to adjust the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. So what do we do? We can easily get away by moving the data from the next node into the current node and then deleting the next node.

......... -> Node(i-1) -> Node(i) -> Node(i+1) -> ...

Video Explanation

Code

Java

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