LeetCode 237 - Delete Node in a Linked List

This problem asks us to delete a node from a singly linked list, but with an unusual restriction: we are not given access to the head of the list. Instead, we are only given a reference to the node that should be deleted.

leetcodemediumlinked-list

LeetCode Problem 237

Difficulty: 🟡 Medium
Topics: Linked List

Solution

Problem Understanding

This problem asks us to delete a node from a singly linked list, but with an unusual restriction: we are not given access to the head of the list. Instead, we are only given a reference to the node that should be deleted.

In a normal linked list deletion operation, we would traverse the list until we find the node immediately before the target node. Then we would update its next pointer to skip the target node. However, that approach is impossible here because we do not have access to the head of the list, and therefore cannot locate the previous node.

The input consists of:

  • A singly linked list.
  • A direct reference to a node inside that list.
  • The given node is guaranteed not to be the last node.

The expected result is that the node's value disappears from the linked list, the list size decreases by one, and the ordering of all remaining nodes stays unchanged.

For example:

4 -> 5 -> 1 -> 9

If the given node is the one containing 5, the final list should become:

4 -> 1 -> 9

The constraints provide several important guarantees:

  • The list always contains at least two nodes.
  • The node to delete is always valid and present in the list.
  • The node to delete is never the tail node.
  • All values are unique.

The guarantee that the node is not the tail node is extremely important. Since we do not have access to the previous node, the only workable strategy depends on having a next node available.

A naive implementation might try to physically remove the current node from memory, but that is impossible without knowing the previous node. Another common mistake is forgetting that the list is singly linked, meaning we cannot traverse backward.

The critical insight is that we do not actually need to remove the current node itself. Instead, we can transform the current node into its successor and then bypass the successor node.

Approaches

Brute Force Approach

The traditional linked list deletion strategy is to start from the head of the list, traverse until reaching the node immediately before the target node, and then reconnect pointers so that the target node is skipped.

For example:

prev -> target -> next

becomes:

prev -> next

This works correctly because removing a node from a singly linked list fundamentally requires modifying the previous node's next pointer.

However, this approach is impossible in this problem because we are not given access to the head node. Without the head, we cannot traverse the list and cannot locate the previous node.

If we somehow had access to the head, the brute force traversal would require linear time.

Optimal Approach

The key observation is that although we cannot remove the current node itself, we can overwrite its contents with the next node's contents.

Suppose the list is:

4 -> 5 -> 1 -> 9

and node points to 5.

We can:

  1. Copy the value from the next node (1) into the current node.
  2. Redirect the current node's next pointer to skip the next node.

After copying:

4 -> 1 -> 1 -> 9

After bypassing the next node:

4 -> 1 -> 9

Effectively, the original node with value 5 disappears from the list.

This works because the problem only cares about the final linked list structure and values, not the actual memory identity of the node object.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Requires access to head, impossible under given constraints
Optimal O(1) O(1) Copies next node data and bypasses next node

Algorithm Walkthrough

  1. Access the next node using node.next.

Since the problem guarantees that the given node is not the tail node, a next node always exists. 2. Copy the next node's value into the current node.

This makes the current node appear identical to the next node. 3. Update the current node's next pointer.

Set:

node.next = node.next.next

This skips over the original next node, effectively removing it from the linked list. 4. The linked list now behaves as though the original node was deleted.

Even though the original node object still exists in memory, its original value no longer exists in the list, which satisfies the problem requirements.

Why it works

The algorithm works because every node in a singly linked list is defined by two things:

  • Its stored value
  • Its pointer to the next node

By copying the next node's value and pointer into the current node, we make the current node indistinguishable from its successor. Then, by bypassing the successor, we effectively erase it from the list. Since the original value disappears and the remaining order stays intact, the deletion is logically correct.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from typing import Optional

class Solution:
    def deleteNode(self, node: "ListNode") -> None:
        """
        :type node: ListNode
        :rtype: void
        """

        node.val = node.next.val
        node.next = node.next.next

The implementation is intentionally very short because the entire trick relies on the problem's special constraints.

The first line copies the next node's value into the current node. After this assignment, the current node now contains the successor's value.

node.val = node.next.val

The second line skips the next node entirely.

node.next = node.next.next

This removes the successor from the linked structure. Since the current node already copied the successor's value, the final list appears exactly as if the original node had been deleted.

The algorithm modifies the list in place and does not return anything, matching the problem requirements.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(node *ListNode) {
    node.Val = node.Next.Val
    node.Next = node.Next.Next
}

The Go implementation follows exactly the same logic as the Python solution.

Since the problem guarantees that node.Next always exists, no nil checking is required. The solution simply copies the next node's value and bypasses the next node.

Unlike some linked list problems, there are no concerns about integer overflow, slices, or dynamic arrays here. The solution only manipulates pointers.

Worked Examples

Example 1

Input:

4 -> 5 -> 1 -> 9

Given node:

5

Initial state:

Current Node Next Node Linked List
5 1 4 -> 5 -> 1 -> 9

Step 1, copy next node value:

node.val = node.next.val

The current node changes from 5 to 1.

List becomes:

4 -> 1 -> 1 -> 9

State after copy:

Current Node Next Node Linked List
1 1 4 -> 1 -> 1 -> 9

Step 2, bypass next node:

node.next = node.next.next

The second 1 node is skipped.

Final list:

4 -> 1 -> 9

Example 2

Input:

4 -> 5 -> 1 -> 9

Given node:

1

Initial state:

Current Node Next Node Linked List
1 9 4 -> 5 -> 1 -> 9

Step 1, copy next value:

node.val = node.next.val

List becomes:

4 -> 5 -> 9 -> 9

Step 2, bypass next node:

node.next = node.next.next

Final list:

4 -> 5 -> 9

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only a constant number of assignments are performed
Space O(1) No extra data structures are used

The algorithm performs only two pointer and value assignments, regardless of the size of the linked list. No traversal occurs, and no additional memory is allocated.

Test Cases

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

def linked_list_to_array(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

# Test 1: Example 1
head = ListNode(4)
head.next = ListNode(5)
head.next.next = ListNode(1)
head.next.next.next = ListNode(9)

Solution().deleteNode(head.next)

assert linked_list_to_array(head) == [4, 1, 9]  # delete middle node

# Test 2: Example 2
head = ListNode(4)
head.next = ListNode(5)
head.next.next = ListNode(1)
head.next.next.next = ListNode(9)

Solution().deleteNode(head.next.next)

assert linked_list_to_array(head) == [4, 5, 9]  # delete another middle node

# Test 3: Minimum valid size
head = ListNode(1)
head.next = ListNode(2)

Solution().deleteNode(head)

assert linked_list_to_array(head) == [2]  # smallest allowed list

# Test 4: Delete second node in three-node list
head = ListNode(10)
head.next = ListNode(20)
head.next.next = ListNode(30)

Solution().deleteNode(head.next)

assert linked_list_to_array(head) == [10, 30]  # simple internal deletion

# Test 5: Negative values
head = ListNode(-5)
head.next = ListNode(-3)
head.next.next = ListNode(-1)

Solution().deleteNode(head.next)

assert linked_list_to_array(head) == [-5, -1]  # handles negative integers

# Test 6: Delete node near tail
head = ListNode(7)
head.next = ListNode(8)
head.next.next = ListNode(9)
head.next.next.next = ListNode(10)

Solution().deleteNode(head.next.next)

assert linked_list_to_array(head) == [7, 8, 10]  # deletion close to tail
Test Why
[4,5,1,9], delete 5 Validates standard middle deletion
[4,5,1,9], delete 1 Ensures deletion works near tail
[1,2], delete 1 Tests smallest valid linked list
[10,20,30], delete 20 Confirms simple internal deletion
[-5,-3,-1], delete -3 Verifies negative values work correctly
[7,8,9,10], delete 9 Tests deletion adjacent to tail

Edge Cases

Deleting a Node in the Smallest Valid List

The smallest allowed linked list contains only two nodes. For example:

1 -> 2

Deleting the first node could expose bugs in implementations that assume longer lists exist. The solution handles this correctly because the first node simply copies the second node's value and bypasses it, leaving a valid single-node list.

Deleting a Node Right Before the Tail

Consider:

7 -> 8 -> 9 -> 10

Deleting 9 means the next node is the tail. Some incorrect implementations may accidentally lose the tail reference or create cycles. This implementation safely copies 10 into the 9 node and then sets next to None, preserving correct list termination.

Attempting to Delete the Tail Node

This is the most important conceptual edge case. If the node were the tail, there would be no next node available to copy from. The algorithm would fail because:

node.next

would be None.

The problem explicitly guarantees this situation never occurs, which is why the constant time solution is possible at all.