Leetcode 237. Delete Node in a Linked List

Problem Explanation

In this problem, we're working with a singly linked list. We're given a node from the list (not the tail), and our goal is to delete that node from the list entirely. We're not asked to return anything, just to modify the linked list as requested.

The challenge here is that, typically, to remove a node from a linked list, we need access to the node before the one we want to remove so we can rewrite its next property (pointer). But here we only have access to the node itself, not to the previous one.

Let's consider an example:

1
2
3Linked list:  4 -> 5 -> 1 -> 9
4Node to delete:  5

The usual approach to delete the node 5 would involve manipulating the next property of node 4. But we can't do that here.

Solution Approach

The way we can solve this is by turning the problem into something a bit different. Instead of trying to delete the given node, we'll effectively delete the next node instead, copying its value into the current node before doing so. It achieves the same effect, because the original node's value is overwritten and then the following node is removed.

Let's use the example above:

  1. Copy the value from node 5 (which is 1) into node 5. The linked list now looks like: 4 -> 1 -> 1 -> 9.
  2. Set the next of node 5 to be next->next, effectively skipping node 1. The linked list now looks like: 4 -> 1 -> 9, which is our expected result.

Here's an illustration:

1
2
3Original:    4 -> 5 -> 1 -> 9
4             |
5            node
6
7After copying:
8             4 -> 1 -> 1 -> 9
9             |
10            node
11
12After deleting:
13             4 -> 1 -> 9
14             |
15            node

Note how we've "moved" the node to delete one position right and then deleted it, while keeping the order of the values in the list intact.

Let's implement this algorithm in different languages.

Python Solution

1
2python
3class Solution:
4    def deleteNode(self, node):
5        node.val = node.next.val  # Copy the value of the next node
6        node.next = node.next.next  # Delete the next node

Java Solution

1
2java
3public class Solution {
4    public void deleteNode(ListNode node) {
5        node.val = node.next.val;  // Copy the value of the next node
6        node.next = node.next.next;  // Delete the next node
7    }
8}

JavaScript Solution

1
2javascript
3class Solution {
4    deleteNode(node) {
5        node.val = node.next.val;  // Copy the value of the next node
6        node.next = node.next.next;  // Delete the next node
7    }
8}

C++ Solution

1
2cpp
3class Solution {
4public:
5    void deleteNode(ListNode* node) {
6        node->val = node->next->val;  // Copy the value of the next node
7        node->next = node->next->next;  // Delete the next node
8    }
9};

C# Solution

1
2csharp
3public class Solution {
4    public void DeleteNode(ListNode node) {
5        node.val = node.next.val;  // Copy the value of the next node
6        node.next = node.next.next;  // Delete the next node
7    }
8}

In all of these solutions, we follow the same algorithm: copy the value from the next node over to the current node, and then remove the next node from the linked list. This successfully "deletes" the original node.## Conclusion

This problem teaches us an important lesson about problem-solving: when we're faced with a situation that seems impossible—that is, deleting a node from a linked list when we only have access to the node itself—we can create a workaround.

By copying the value from the next node and then deleting it, we effectively delete the current node. What's more, even though our approach involved manipulating the next node, from an outsider's view, it appears as if we've deleted the current node. That's because the original node's value is overwritten before the next node is removed.

These kinds of solutions which involve clever "hacks" or workarounds are common in computer science and programming. They often require a good understanding of the problem and the data structures involved, as well as creative thinking.

So, the next time you're faced with a problem that seems impossible to solve, consider whether there's a different way to frame the problem—or whether there's a clever workaround that will let you achieve the same result.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫