Delete the Middle Node of a Linked List | Leetcode 2095 | Modified Tortoise and Hare

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

• For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Here’s the [Problem Link] to begin with.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node. 

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 1 <= Node.val <= 105

Solution: Optimal Approach (Modified Tortoise and Hare)

Intuition

Imagine you have two friends running on a track where one runs twice as fast as the other. When the faster friend finishes, the slower friend will be at the middle! But here’s the twist – we want to delete the middle node, so we need the slower friend to stop just before the middle. It’s like having a security guard positioned right before the middle to “remove” the middle person from the line.

Detailed Approach

1. Handle Edge Case: If there’s only one node, return null (delete the only node)
2. Set Up Two Pointers: Create slow and fast pointers, both starting at head
3. Give Fast Pointer Head Start: Move fast pointer two steps ahead initially
4. Move Both Pointers: Move slow 1 step and fast 2 steps until fast reaches the end
5. Perfect Positioning: When fast reaches the end, slow will be just before the middle node
6. Delete Middle: Skip the middle node by updating slow’s next pointer

Code

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Handle edge case: single node list
        if not head.next:
            return None  # Delete the only node, return empty list
        
        slow = head          # Slow pointer (tortoise)
        fast = head          # Fast pointer (hare)
        fast = fast.next.next  # Give fast pointer a 2-step head start
        
        # Move pointers until fast reaches the end
        while fast and fast.next:
            slow = slow.next      # Move slow pointer 1 step
            fast = fast.next.next # Move fast pointer 2 steps
        
        # Delete the middle node by skipping it
        slow.next = slow.next.next
        return head

Code Explanation

This solution uses a clever modification of the classic tortoise and hare algorithm. Instead of starting both pointers at the same position, we give the fast pointer a two-step head start. This ensures that when the fast pointer reaches the end, the slow pointer is positioned exactly one node before the middle node. This positioning is crucial because we need to access the node before the middle to delete the middle node by updating its next pointer.

Dry Run

Let’s trace through: 1 -> 2 -> 3 -> 4 -> 5

Initial Setup:

• slow = 1, fast = 1
• Give fast head start: fast = 3
• Current state: slow at 1, fast at 3

Step 1:

• fast = 5, fast.next = None
• slow = 2, fast = 5
• Continue (fast exists, fast.next is None)

Step 2:

• Loop ends because fast.next is None
• slow = 2 (positioned before middle node 3)

Delete Middle:

• slow.next = 3, slow.next.next = 4
• Set slow.next = 4 (skip node 3)
• Final result: 1 -> 2 -> 4 -> 5

Result: Middle node 3 is successfully deleted!

Let’s also trace a shorter example: 1 -> 2 -> 3

Initial Setup:

• slow = 1, fast = 1
• Give fast head start: fast = 3
• Current state: slow at 1, fast at 3

Check Loop Condition:

• fast = 3 (exists), fast.next = None
• Loop doesn’t execute

Delete Middle:

• slow = 1, slow.next = 2
• Set slow.next = 2.next (which is 3)
• Final result: 1 -> 3

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list once, visiting each node at most once
• Space Complexity: O(1) – We only use two pointer variables, no extra space needed

Simplifying It

This approach is like having a smart assistant who knows exactly where to stand to help you remove the middle person from a line. By giving the fast pointer a head start, we ensure the slow pointer stops at the perfect position – right before the middle. It’s an elegant solution that solves the problem in one pass without needing to count the total length first.

Key Insights

Why the head start matters:
In the classic tortoise and hare algorithm, both pointers start together, and when fast reaches the end, slow is at the middle. But since we want to delete the middle node, we need slow to be before the middle. The two-step head start achieves this perfectly!

Edge case handling:
The special check for single-node lists is important because there’s no “before middle” position in a single-node list. We simply return null to indicate an empty list.

Summary

This optimal solution efficiently solves the problem in a single pass using constant space. The key insight is the clever modification of the classic two-pointer technique to position the slow pointer exactly where we need it for deletion. This approach demonstrates how small changes to well-known algorithms can solve related problems elegantly!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.