연결된 목록에서 노드 삭제

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

Enter fullscreen mode Exit fullscreen mode

Initial Thought

Normally we delete a node like this:

prev.next = node.next

Enter fullscreen mode Exit fullscreen mode

But here:

We don't have prev
We don't have head

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

We need to delete:

5

Enter fullscreen mode Exit fullscreen mode

Instead of removing node 5, copy the value of the next node into it.

4 -> 1 -> 1 -> 9

Enter fullscreen mode Exit fullscreen mode

Now remove the next node.

4 -> 1 -> 9

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Current node:

5

Enter fullscreen mode Exit fullscreen mode

Next node:

1

Enter fullscreen mode Exit fullscreen mode

Step 1

Copy next node value.

node.val = node.next.val

Enter fullscreen mode Exit fullscreen mode

List becomes:

4 -> 1 -> 1 -> 9

Enter fullscreen mode Exit fullscreen mode

Step 2

Skip next node.

node.next = node.next.next

Enter fullscreen mode Exit fullscreen mode

List becomes:

4 -> 1 -> 9

Enter fullscreen mode Exit fullscreen mode

Done.

Optimal Java Solution

class Solution {
    public void deleteNode(ListNode node) {

        ListNode cur = node.next;

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

Enter fullscreen mode Exit fullscreen mode

Even Shorter Version

class Solution {
    public void deleteNode(ListNode node) {

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

Enter fullscreen mode Exit fullscreen mode

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.