Middle of the Linked List

Intuition

If one pointer moves a single step at a time while another moves two steps at a time, the faster one reaches the end exactly when the slower one reaches the center. This works because after k iterations the slow pointer has traveled k nodes and the fast pointer has traveled 2k nodes. The moment the fast pointer runs out of room (it becomes null or its next is null), the slow pointer is sitting on the middle. Starting both at the head naturally returns the second middle for even-length lists, which is exactly what we want. It needs only one traversal and a couple of pointers.

Algorithm walkthrough

1. 1Initialize both slow and fast to point at the head of the list.
2. 2Loop while fast is not null and fast.next is not null.
3. 3On each iteration, move slow forward by one node and fast forward by two nodes.
4. 4When the loop condition fails, fast has passed the end and slow has reached the middle.
5. 5Return slow, which for even lengths is the second of the two middle nodes.

Implementation

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow