Delete Node in a Linked List

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.
No previous pointer.

So how do we remove it?

Let's understand the trick.

---

Problem Statement

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.

Example

Input:
4 -> 5 -> 1 -> 9

node = 5

Output:
4 -> 1 -> 9

---

Initial Thought

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.

---

Key Observation

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.

---

Intuition

1. Copy the next node's value into the current node.
2. Skip the next node.
3. 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.

---

Dry Run

Input

4 -> 5 -> 1 -> 9

node = 5

Current node:

5

Next node:

1

Step 1

Copy next node value.

node.val = node.next.val

List becomes:

4 -> 1 -> 1 -> 9

---

Step 2

Skip next node.

node.next = node.next.next

List becomes:

4 -> 1 -> 9

Done.

---

Optimal Java Solution

class Solution {
    public void deleteNode(ListNode node) {

        ListNode cur = node.next;

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

---

Even Shorter Version

class Solution {
    public void deleteNode(ListNode node) {

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

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(1)
Space Complexity	O(1)

---

Why Does This Work?

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.

---

Interview Takeaway

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.