Delete Node in a Linked List

Source: Dev.to

Problem Link - https://leetcode.com/problems/delete-node-in-a-linked-list/ This is one of those interview questions that looks impossible at first. Normally, to delete a node from a Linked List, we need access to the previous node. But in this problem, we’re only given the node that needs to be deleted. No head. So how do we remove it? Let’s understand the trick. Write a function to delete a node in a singly linked list. You are not given the head of the list. Instead, you are given only the node that needs to be deleted. Input: 4 -> 5 -> 1 -> 9

node = 5

Output: 4 -> 1 -> 9

Normally we delete a node like this: prev.next = node.next

But here: We don’t have prev We don’t have head

So the usual deletion approach is impossible. Although we cannot delete the current node directly, we can make it look like it never existed. Consider: 4 -> 5 -> 1 -> 9

We need to delete: 5

Instead of removing node 5, copy the value of the next node into it. 4 -> 1 -> 1 -> 9

Now remove the next node. 4 -> 1 -> 9

The original value 5 has disappeared. Mission accomplished. Copy the next node’s value into the current node. Skip the next node. The current node now behaves as if it was deleted. Since the problem guarantees that the given node is not the tail node, a next node will always exist. 4 -> 5 -> 1 -> 9

node = 5

Current node: 5

Next node: 1

Copy next node value. node.val = node.next.val

List becomes: 4 -> 1 -> 1 -> 9

Skip next node. node.next = node.next.next

List becomes: 4 -> 1 -> 9

Done. class Solution { public void deleteNode(ListNode node) {

    ListNode cur = node.next;

    node.val = cur.val;
    node.next = cur.next;
}

}

class Solution { public void deleteNode(ListNode node) {

    node.val = node.next.val;
    node.next = node.next.next;
}

}

Metric Complexity

Time Complexity O(1)

Space Complexity O(1)

We are not actually deleting the given node. Instead: We overwrite its value with the next node’s value. Then remove the next node from the chain. As a result, the linked list behaves exactly as if the target node was deleted. The trick is realizing that deleting the given node is impossible without access to its previous node. So instead of deleting the node, we transform it into its next node and delete that next node instead. This is one of the most elegant O(1) Linked List tricks asked in interviews. This problem teaches an important interview lesson: Sometimes the solution is not about doing what the problem asks directly, but about achieving the same final state using a clever observation.