How do you solve Delete the Middle Node of a Linked List on LeetCode?

Delete the Middle Node of a Linked List (LeetCode #2095) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using two pointers can significantly reduce the number of traversals needed.

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

The optimal solution for Delete the Middle Node of a Linked List runs in O(n) time and uses O(1) space. The time complexity is O(n) because we traverse the list only once. The space complexity is O(1) since we only use a few pointers.

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

The brute force approach for Delete the Middle Node of a Linked List is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves traversing the linked list to find its length, then calculating the index of the middle node, and finally reconstructing the list without that node. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Delete the Middle Node of a Linked List?

Delete the Middle Node of a Linked List uses the following concepts: Linked List, Two Pointers. The recommended patterns to study are: Two Pointers, Linked List Manipulation.

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

Always clarify the problem and edge cases with the interviewer. Explain your thought process as you code to show your understanding. Consider both time and space complexity in your solutions.

What are common mistakes when solving Delete the Middle Node of a Linked List?

Not handling edge cases like a single-node list. Forgetting to update the previous node's next pointer when removing the middle node.

#2095

Delete the Middle Node of a Linked List

Medium

Linked ListTwo PointersTwo PointersLinked List Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

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

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses two pointers to find the middle node while keeping track of the previous node. This approach is efficient and only requires a single pass through the list.

⚙️

Algorithm

3 steps

1Step 1: Initialize two pointers, slow and fast. Slow moves one step at a time, while fast moves two steps.
2Step 2: As you traverse, keep track of the previous node to the slow pointer.
3Step 3: When the fast pointer reaches the end, the slow pointer will be at the middle node. Adjust the previous node's next pointer to skip the middle node.

solution.py17 lines

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def deleteMiddle(head):
7    if not head or not head.next:
8        return None
9    slow = head
10    fast = head
11    prev = None
12    while fast and fast.next:
13        prev = slow
14        slow = slow.next
15        fast = fast.next.next
16    prev.next = slow.next
17    return head

ℹ

Complexity note: The time complexity is O(n) because we traverse the list only once. The space complexity is O(1) since we only use a few pointers.

1Using two pointers can significantly reduce the number of traversals needed.
2Maintaining a reference to the previous node is crucial for modifying the list.

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