How do you solve Delete Node in a Linked List on LeetCode?

Delete Node in a Linked List (LeetCode #237) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: The node to be deleted is guaranteed to not be the last node.

What is the time complexity of Delete Node in a Linked List?

The optimal solution for Delete Node in a Linked List runs in O(1) time and uses O(1) space. This complexity is constant because we only perform a fixed number of operations regardless of the size of the linked list.

What is the brute force solution for Delete Node in a Linked List?

The brute force approach for Delete Node in a Linked List is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we traverse the linked list to find the node before the one we want to delete. Then, we adjust the pointers to skip the node we want to delete. This is straightforward but involves unnecessary traversal. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Delete Node in a Linked List?

Delete Node in a Linked List uses the following concepts: Linked List. The recommended patterns to study are: Pointer Manipulation, Linked List.

What are the interview tips for Delete Node in a Linked List?

Understand the problem constraints clearly. Think about how you can manipulate pointers directly. Practice explaining your thought process as you code.

What are common mistakes when solving Delete Node in a Linked List?

Students often try to traverse the list to find the previous node, which is unnecessary. Some may forget to handle the pointer adjustment correctly.

#237

Delete Node in a Linked List

Medium

Linked ListPointer ManipulationLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

Instead of traversing the list to find the previous node, we can directly copy the value from the next node into the current node and then skip the next node. This is efficient and works in one pass.

⚙️

Algorithm

3 steps

1Step 1: Copy the value from the next node into the current node.
2Step 2: Change the next pointer of the current node to skip the next node.
3Step 3: The next node is effectively deleted.

solution.py9 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def deleteNode(node):
8    node.val = node.next.val
9    node.next = node.next.next

ℹ

Complexity note: This complexity is constant because we only perform a fixed number of operations regardless of the size of the linked list.

1The node to be deleted is guaranteed to not be the last node.
2We can manipulate the pointers directly to achieve deletion without needing the head.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.