237. Delete Node in a Linked List

MediumLinked List
Leetcode Link

Problem Description

In this problem, we're tasked with deleting a specific node from a singly-linked list, but with a twist: we're only given access to that particular node, not the head of the list. Moreover, the given node will not be the list's tail, and all node values in the list are unique. What makes this task unique is that typically, to remove a node from a linked list, we would need access to the node before the one we want to delete to adjust the next pointer. However, since we're only given the target node itself (and guaranteed it's not the last one), we need a different strategy. Our goal is to remove the node from the list while preserving the order of remaining nodes. It's important to understand that "deleting the node" here means ensuring the value of the said node doesn't appear in the linked list sequence, and the length of the linked list is decreased by one.

Intuition

Understanding the constraints and the standard operations on a linked list is key to solving this problem. Given that we cannot directly remove the target node by changing its previous node's next pointer (because we don't have access to it), we can use a clever trick: copy the value from the next node into the target node, and then remove the next node instead. This effectively overwrites the target node's value with its successor's value, and then deleting the successor (which we have access to) achieves the goal of removing the target node's value from the list. The key realization here is that we're not actually deleting the given node, but rather, we're making it a clone of the next node in terms of value, then skipping over the next node, effectively removing its presence from the list.

Learn more about Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The solution takes advantage of the properties of a singly-linked list and uses the constraint that is provided: We are given access to the node that must be deleted, and it is not the last node of the list.

Here's the step-by-step approach that is used in the solution:

  1. Copy the value from the next node into the current node. This is done by using the statement node.val = node.next.val. After this step, the current node (node) and the next node (node.next) have the same value, the one that was originally in node.next.

  2. Delete the next node from the linked list. This doesn't mean removing it from memory, since Python's garbage collector will take care of that eventually. We simply need to change the reference of the current node's next to skip the next node and point to the node following it. We accomplish this with node.next = node.next.next.

By performing these two steps, we've essentially shifted the value from the node.next to node, and then we unlink node.next from the chain. Visually, if our list was A -> B -> C -> D and we wanted to delete B, we make B take on the value and position of C, resulting in A -> C -> D. Then B (with the value of C) is no longer part of the list. This fulfills all the requirements for the deletion operation as per the problem statement.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's assume we have a singly-linked list that looks as follows:

14 -> 5 -> 1 -> 9

And we're asked to delete the node with value 5 from it. We do not have access to the head of the list, only to the target node. Here's how we would solve it using the solution approach:

  1. We start with the node we want to delete, which has the value 5. The list looks like this:

    14 -> 5 -> 1 -> 9

  2. According to our 1st step in the solution approach, we copy the value of the next node (1) into the current node (5). Our list will then look like this:

    14 -> 1 -> 1 -> 9

    Now, the node we wanted to delete (5) has been overwritten with the value of 1.

  3. Next, we perform the 2nd step in our solution where we unlink the node after the current node (the second 1). This is done by setting the next pointer of our current node to the next of the next node. After this step, the list now looks like this:

    14 -> 1 -> 9

  4. The node originally containing 5 has now been removed (or rather its value copied over and its successor unlinked), and our linked list preserves the original order with the target node no longer present.

The deletion is successful and has been performed using the given access constraints. The linked list now correctly contains the sequence 4 -> 1 -> 9.

Solution Implementation

1# Definition for a singly-linked list node.
2class ListNode:
3    def __init__(self, value):
4        self.value = value  # Initialize node's value
5        self.next = None    # Next node reference
6
7
8class Solution:
9    def deleteNode(self, node):
10        """
11        Delete a node from a singly-linked list, given only access to that node.
12      
13        :param node: The node to be deleted from the linked list.
14        :type node: ListNode
15        """
16        node.value = node.next.value  # Copy the value from the next node to the current node
17        node.next = node.next.next    # Bypass the next node by pointing to the node after next
18
1// Class definition for a singly-linked list node.
2class ListNode {
3    int val; // The value of the node.
4    ListNode next; // Reference to the next node in the list.
5
6    // Constructor to initialize the node with a value.
7    ListNode(int x) {
8        val = x;
9    }
10}
11
12// Class containing the solution method.
13class Solution {
14    /**
15     * Deletes a node (except the tail) from a singly-linked list, given only access to that node.
16     * The input node should not be the tail, and the list should have at least two elements.
17     * @param node the node to be deleted
18     */
19    public void deleteNode(ListNode node) {
20        // Copy the value of the next node into the current node.
21        node.val = node.next.val;
22        // Set the current node's next pointer to skip the next node, effectively deleting it.
23        node.next = node.next.next;
24    }
25}
26
1// Definition for singly-linked list node.
2struct ListNode {
3    int val;          // The value of the node.
4    ListNode *next;   // Pointer to the next node in the list.
5
6    // Constructor to initialize a ListNode with a value and optional link to the next node.
7    ListNode(int x) : val(x), next(nullptr) {} // Using nullptr instead of NULL
8};
9
10class Solution {
11public:
12    // Deletes the given node (except the tail) from the linked list.
13    // node represents the node to be deleted.
14    void deleteNode(ListNode* node) {
15        // This function assumes that the node to delete is not the tail
16        // and that we are not handling edge cases where node could be null.
17
18        // Copy the value from the next node to the current node.
19        node->val = node->next->val;
20
21        // Save the next next node, which will be the new next after deletion.
22        ListNode* next_next = node->next->next;
23
24        // Delete the next node, effectively removing it from the list.
25        delete node->next;
26
27        // Make the next pointer of the current node point to the new next node (next_next).
28        node->next = next_next;
29    }
30};
31
1// Given the node to be deleted (except the tail), this function will delete the node in place.
2function deleteNode(node: ListNode | null): void {
3    if (node === null || node.next === null) {
4        // If the node is null or it is the tail node, do nothing since deletion is not possible.
5        return;
6    }
7    // Copy the value from the next node to the current node.
8    node.val = node.next.val;
9    // Bypass the next node by pointing the current node's `next` reference to the next node's `next`.
10    node.next = node.next.next;
11}
12
Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Time and Space Complexity

The time complexity of the code is O(1). This is because it takes a constant amount of time to copy the value from the next node to the given node and to update the next pointer of the given node. No loops or recursive calls are involved.

The space complexity of the code is O(1). No extra space is used that is dependent on the size of the input. Only pointers are reassigned which does not require additional space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

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 👨‍🏫