Delete the Middle Node of a Linked List – LeetCode75 Explained in Python

Linked lists are one of the most fundamental data structures in computer science and form the backbone of many real-world systems. The Delete the Middle Node of a Linked List problem (LeetCode75) is an excellent exercise to practice two-pointer techniques, linked list traversal and node manipulation. It is not only common in coding interviews but also essential for understanding how linked lists operate at a deeper level.

In this blog, we’ll break down the problem, analyze examples and provide a complete Python solution with step-by-step explanations. By the end, you’ll gain confidence in handling linked list problems and be better prepared for technical interviews.

Problem Statement

You are given the head of a linked list. Your task is to delete the middle node of the linked list and return the head of the modified list.

If the list has n nodes, the middle node is defined as the ⌊n / 2⌋-th node (0-indexed).
If the list has only one node, return None.

Understanding the Problem

The challenge lies in locating the middle node without explicitly counting all nodes in advance. While one approach is to traverse the list twice (once to count, once to delete), a more efficient approach is to use the fast and slow pointer method.

Here’s how it works:

Use a slow pointer that moves one step at a time.
Use a fast pointer that moves two steps at a time.
When the fast pointer reaches the end, the slow pointer will be at the middle node.
Keep track of the node before the slow pointer to perform deletion.

Examples

Example 1

Input: head = [1, 3, 4, 7, 1, 2, 6]
Output: [1, 3, 4, 1, 2, 6]
Explanation: The middle node is 7. After deleting, the list becomes 1 → 3 → 4 → 1 → 2 → 6.

Example 2

Input: head = [1, 2, 3, 4]
Output: [1, 2, 4]
Explanation: The middle node is 3. After deletion, we have 1 → 2 → 4.

Example 3

Input: head = [2, 1]
Output: [2]
Explanation: The middle node is 1. Only 2 remains.

Complete Python Solution

from typing import Optional

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

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        
        slow = head
        fast = head
        prev = None

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        if prev:
            prev.next = slow.next
        else:
            head = slow.next
        
        return head

Step-by-Step Explanation

Step 1: Handle Edge Case

If the list has only one node, deleting it means returning None.

if not head or not head.next:
    return None

Step 2: Initialize Pointers

We set both slow and fast pointers at the head. We also keep prev to track the node before slow.

slow = head
fast = head
prev = None

Step 3: Move Pointers

Move slow one step.
Move fast two steps.
When fast reaches the end, slow will be at the middle.

while fast and fast.next:
    prev = slow
    slow = slow.next
    fast = fast.next.next

Step 4: Delete the Middle Node

Point prev.next to slow.next, effectively removing slow from the list.

if prev:
    prev.next = slow.next
else:
    head = slow.next

Step 5: Return Modified List

Finally, return the updated head of the linked list.

return head

Time and Space Complexity

Time Complexity: O(n) → Each node is visited once.
Space Complexity: O(1) → We only use pointers, no extra memory.

Edge Cases

Single Node List: Input [5] → Output None.
Two Node List: Input [1, 2] → Output [1].
Even Length List: Input [1, 2, 3, 4] → Output [1, 2, 4].
Odd Length List: Input [1, 3, 4, 7, 1, 2, 6] → Output [1, 3, 4, 1, 2, 6].

Real-World Applications

Deleting a middle element in a linked list may sound simple but it mimics many real-world scenarios:

Memory management systems where linked lists track allocated blocks and nodes must be deleted efficiently.
Social media feeds where posts are dynamically removed while maintaining the sequence.
Task scheduling systems that reassign jobs when a middle task is canceled.
Data stream processing where mid-sequence data points are discarded without disrupting flow.

Conclusion

The Delete the Middle Node of a Linked List problem (LeetCode75) is a great way to practice two-pointer techniques and deepen your understanding of linked list operations. By using a fast and slow pointer, we efficiently find and delete the middle node in a single traversal.

Mastering this challenge builds confidence in manipulating linked lists, a skill that’s frequently tested in coding interviews and crucial in real-world systems like memory allocation, data streams and task scheduling.

References

3 thoughts on “Delete the Middle Node of a Linked List – LeetCode75 Explained in Python”

Pingback: Odd Even Linked List – LeetCode75 Python Solution Explained - Vanita.ai
Pingback: Reverse Linked List – LeetCode75 Python Solution Explained - Vanita.ai
Pingback: Maximum Twin Sum of a Linked List – LeetCode75 Python Solution Explained - Vanita.ai