Middle of the Linked List

The problem description can be found in LeetCode.

Approach

A naive approach would consist of storing all the nodes values to a classic list and then returning the middle element. However, this would require $O(n)$ space, where $n$ is the number of nodes in the Linked Lists.

In order to use no additional space, we can apply the Floyd's tortoise and hare algorithm, that we already applied in the Linked List Cycle problem.

Solution

from typing import Optional


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

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the nums list.