Problem Statement in English

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

Approach

We can do better than counting the number of nodes in the linked list first and then deleting the middle node. We can use the fast and slow pointer technique to find the middle node in one pass.

The idea is that we can have two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.

An edge case to consider is when the linked list has only one node. In that case, we can simply return None since deleting the middle node would leave us with an empty list.

The while loop to iterate through the linked list while the fast pointer and its next node are not None ensures that we correctly identify the middle node even when the linked list has an even number of nodes.

And we’re done!

Solution in Python


class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Edge case: If there's only one node, deleting it returns None
        if not head or not head.next:
            return None
        
        # Initialize slow at head, and fast two steps ahead
        slow = head
        fast = head.next.next
        
        # Move fast by 2 and slow by 1
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            
        # slow is now right BEFORE the middle node
        slow.next = slow.next.next
        
        return head

Complexity

  • Time: $O(n)$
    Since we need to traverse the linked list once to find the middle node, the time complexity is linear with respect to the number of nodes in the list.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space for the slow and fast pointers, the space complexity is constant.

And we are done.