LeetCode: Delete the Middle Node of a Linked List

Delete the middle node of a linked list.

Posted on LeetCode Python

Solution

Track two pointers, slow and fast. Move fast two nodes for every one node that slow moves. When fast reaches the end of the list, slow will be at the node before the middle node.

Algorithm example

You will notice that slow is one node ahead. Let’s introduce prev to keep track of the node before slow.

Runtime

43 ms | Beats 90.29% 

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return None


        slow = head
        fast = head
        prev = None


        while fast is not None and fast.next is not None:
            prev = slow
            slow = slow.next
            fast = fast.next.next


        if prev and prev.next:
          prev.next = prev.next.next


        return head