LeetCode 237: Delete Node in a Linked List Solution in Python – A Step-by-Step Guide

What Is LeetCode 237: Delete Node in a Linked List?

In LeetCode 237: Delete Node in a Linked List, you’re given a node within a singly linked list (not the tail), and your task is to delete it. Unlike typical linked list deletion, you don’t have access to the head or previous node—only the node to delete. This contrasts with tree problems like LeetCode 236: Lowest Common Ancestor of a Binary Tree, focusing on in-place linked list manipulation.

Problem Statement

• Input: A node in a singly linked list (not the tail).
• Output: None (modify the list in-place to delete the node).
• Rules: No access to head; node is guaranteed not to be the last.

Constraints

• Number of nodes: 2 to 10^5.
• Node values: -10^3 to 10^3.
• Node is not the tail and exists in the list.

Examples

• Input: head = [4,5,1,9], node = 5
• Before: 4->5->1->9
• After: 4->1->9
• Input: head = [4,5,1,9], node = 1
• Before: 4->5->1->9
• After: 4->5->9

Understanding the Problem: Deleting Without Head Access

To solve LeetCode 237: Delete Node in a Linked List in Python, we need to remove a node without a reference to its predecessor, which is unusual for linked list deletion. This isn’t about counting digits like LeetCode 233: Number of Digit One—it’s about manipulating pointers or values in-place. Since we can’t re-link the previous node, we must get creative. We’ll explore two approaches: 1. Best Solution (Value Swap): O(1) time, O(1) space—tricky but efficient. 2. Alternative Solution (Dummy Node with Full Traversal): O(n) time, O(1) space—hypothetical, as we don’t have head access, but useful for understanding.

Let’s start with the best solution.

Best Solution: Value Swap Approach

Why This Is the Best Solution

The value swap approach is our top choice for LeetCode 237 because it solves the problem in constant time and space by cleverly copying the next node’s value into the node to delete, then bypassing it. It’s the intended solution given the problem’s constraints, making it both efficient and elegant.

How It Works

• Since we can’t access the previous node, copy the value of the next node into the current node.
• Update the current node’s next pointer to skip the next node, effectively deleting it.
• The list’s structure adjusts, and the original node’s identity is preserved while its value is replaced.

Step-by-Step Example

Example 1: head = [4,5,1,9], node = 5

• List: 4->5->1->9
• Node to Delete: 5
• Process:
• Copy 1 into 5’s value: 4->1->1->9 (node 5 now has value 1).
• Skip next node: 5.next = 1.next → 4->1->9 (original 5 node remains, but list is 4->1->9).
• Result: 4->1->9

Example 2: head = [4,5,1,9], node = 1

• List: 4->5->1->9
• Node to Delete: 1
• Process:
• Copy 9 into 1: 4->5->9->9
• Skip next node: 1.next = 9.next → 4->5->9
• Result: 4->5->9

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

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

class Solution:
    def deleteNode(self, node):
        # Line 1: Copy next node’s value
        node.val = node.next.val  # e.g., 5 becomes 1

        # Line 2: Skip next node
        node.next = node.next.next  # e.g., 5->9, bypassing original 1

• Line 1: Overwrites the node’s value with the next node’s value (e.g., 5 becomes 1).
• Line 2: Updates the next pointer to skip the next node, effectively deleting it.
• Time Complexity: O(1) – constant time operations.
• Space Complexity: O(1) – no extra space.

Alternative Solution: Dummy Node with Full Traversal (Hypothetical)

Why an Alternative Approach?

The dummy node with full traversal approach is a hypothetical alternative because the problem doesn’t provide the head, but it’s worth exploring for understanding typical linked list deletion. It assumes head access, using a dummy node to track the previous node and delete the target traditionally. It’s a great learning tool despite not fitting the problem’s exact constraints.

How It Works (If Head Were Available)

• Create a dummy node pointing to head.
• Traverse to find the node to delete, keeping track of the previous node.
• Update the previous node’s next pointer to skip the target node.

Step-by-Step Example (Hypothetical)

Example: head = [4,5,1,9], node = 5 (assuming head access)

• List: 4->5->1->9
• Process:
• Dummy->4, prev = 4, curr = 5.
• Found 5: prev.next = curr.next → 4->1->9.
• Result: 4->1->9

Code for Dummy Node Approach (Hypothetical)

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

class Solution:
    def deleteNode(self, head: ListNode, node: ListNode) -> ListNode:
        # Line 1: Create dummy node (assuming head access)
        dummy = ListNode(0)
        dummy.next = head
        curr = head
        prev = dummy

        # Line 2: Traverse to find node
        while curr and curr != node:
            prev = curr
            curr = curr.next

        # Line 3: Delete node
        if curr:
            prev.next = curr.next

        # Line 4: Return updated head
        return dummy.next

• Note: This doesn’t work for LeetCode 237 as-is because we lack head access; it’s a conceptual alternative.
• Time Complexity: O(n) – traverses list.
• Space Complexity: O(1) – only pointers.

Comparing the Two Solutions

• Best Solution (Value Swap):
• Pros: O(1) time and space, fits problem constraints.
• Cons: Doesn’t truly “delete” the node’s memory, just its value.
• Alternative Solution (Dummy Node with Traversal):
• Pros: Traditional deletion, clear logic.
• Cons: Requires head (not provided), O(n) time.

The value swap method is our best as it’s the only viable solution given the problem’s setup.

Additional Examples and Edge Cases

Middle Node

• Input: [1,2,3,4], node = 2
• Output: 1->3->4

First Node (Not Tested, as Head Not Given)

• Input: [1,2,3], node = 1 (hypothetical)
• Best solution still works if next exists.

Constraints Handling

• Problem guarantees node isn’t tail, so next always exists.

Complexity Breakdown

• Value Swap:
• Time: O(1).
• Space: O(1).
• Dummy Node (Hypothetical):
• Time: O(n).
• Space: O(1).

Value swap is superior given constraints.

Key Takeaways for Beginners

• Linked List Deletion: Usually needs prev, but here we adapt.
• Value Swap: Copies and skips in-place.
• Traversal: Traditional method needs head.
• Python Tip: Pointer manipulation—see [Python Basics](/python/basics).

Final Thoughts: Delete Nodes Like a Pro

LeetCode 237: Delete Node in a Linked List in Python is a clever linked list puzzle. The value swap solution shines with its O(1) brilliance, while the dummy node approach offers a traditional lens (if head were available). Want more linked list challenges? Try LeetCode 206: Reverse Linked List or LeetCode 21: Merge Two Sorted Lists. Ready to delete? Head to Solve LeetCode 237 on LeetCode and remove that node today!