Leetcode 2095. Delete the Middle Node of a Linked List

LeetCode 2095

 Linked lists can be intimidating when you first start learning Data Structures and Algorithms. You can't just jump to the middle of the list like you can with a standard array; you have to traverse it step-by-step.

Today, we are going to break down LeetCode 2095: Delete the Middle Node of a Linked List. We will look at a simple, easy-to-understand Python solution and walk through it line-by-line so you can see exactly how it works.

Understanding the Problem

The problem gives us the head (the very first node) of a linked list. Our goal is to find the middle node, delete it, and return the modified list.

How do we define the "middle"? If the list has n nodes, the middle is the ⌊n / 2⌋th node (using 0-based indexing).

• If your list has 5 nodes (Indices 0, 1, 2, 3, 4), the middle is 5 / 2 = 2. We want to delete the node at index 2.

• If your list has 4 nodes (Indices 0, 1, 2, 3), the middle is 4 / 2 = 2. We still want to delete the node at index 2.

class Solution:

    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # Step 1: Handle the edge case (only 1 node)

        if not head.next:

            return None

            

        # Step 2: First pass to count the total nodes

        mid, p = 0, head

        while p:

            mid, p = mid + 1, p.next

            

        # Step 3: Calculate steps to the node exactly BEFORE the middle

        mid, p = mid // 2 - 1, head

        

        # Step 4: Second pass to reach that node

        while mid:

            mid, p = mid - 1, p.next

            

        # Step 5: Delete the middle node by skipping it

        p.next = p.next.next

        

        return head

Step-by-Step Breakdown

1. The Base Case (Handling tiny lists):

Before we do any heavy lifting, we need to check if the list only has a single node. head.next looks at the second node. If there is no second node (not head.next), the list size is 1. Since the middle of 1 node is that exact node itself, we delete it by simply returning None (an empty list).

2. The First Pass (Counting the nodes)

Because this is a linked list, we don't know how long it is. We have to count it manually!

• We create a variable mid (which is actually acting as our total node counter here) and start it at 0.

• We create a pointer p and start it at the head of the list.

• The while p: loop moves our pointer forward one step at a time (p = p.next) and adds 1 to our counter (mid = mid + 1) until we hit the end of the list. By the end of this loop, mid holds the total number of nodes.

3. The Math (Finding our stopping point)

To delete a node in a linked list, you can't just stand on the node you want to delete. You have to stand on the node right before it so you can change where its "next" pointer points.

• mid // 2 gives us the exact index of the middle node.

• Subtracting 1 (mid // 2 - 1) gives us the number of steps we need to take from the head to land exactly one node before the middle.

• We overwrite our mid variable with this new target number, and we reset our p pointer back to the head to start our second journey.

4. The Second Pass (Walking to the target)

Now we just walk forward again! Every time we take a step (p = p.next), we subtract 1 from mid. When mid hits 0, the loop stops. At this exact moment, p is pointing to the node immediately preceding our middle node.

5. The Deletion (Pointer magic!)

This is the magic line of linked lists. Currently, p is pointing to the middle node. We simply tell p to let go of the middle node, and instead, grab the hand of the node after the middle one (p.next.next). Because nothing is pointing to the middle node anymore, it is effectively deleted from our chain!

Note: Finally, we return head to give back our brand new, modified linked list!

Complexity Check

• Time Complexity: O(N). We iterate through the list one and a half times (once fully to count, and once halfway to delete). In Big O notation, we drop the constants, leaving us with a linear time complexity of O(N).

• Space Complexity: O(1). We are only using two variables (mid and p) to keep track of numbers and positions. We aren't creating any new arrays or data structures, so our memory usage is constant.

IF YOU HAVE ANY DOUBT PLEASE LET ME KNOW IN THE COMMENTS!!!