Valizada's blog

237. Delete Node in a Linked List - June day 2

Linked list problem that can be solved in O(1)

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Given linked list -- head = [4,5,1,9], which looks like following:

Note:

The linked list will have at least two elements.
All of the nodes' values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Do not return anything from your function.

Example 1

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.

This is a trick problem - why leetcode?

The question is asking to delete a node but there is not really a proper way to do it without doubly linked list. What leetcode expects is really to change a value of a node.

From the description we know that the node wont be the tail, hence without worrying about null pointer we can take the value of the next node and assign to the current one:

  1. Assign the value of the next node to the given
  2. Point next of the given node to the next of next: next.next
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}