Middle Element Detection

Slow/fast again: advance fast twice as fast as slow; when fast ends, slow is near the middle (define even-length tie-breaking).

Try this in Python

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class Node:
    val: int
    next: Node | None = None


def to_list(head: Node | None) -> list[int]:
    out: list[int] = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def from_list(vals: list[int]) -> Node | None:
    dummy = Node(0)
    cur = dummy
    for x in vals:
        cur.next = Node(x)
        cur = cur.next
    return dummy.next


def middle(head: Node | None) -> int | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next  # type: ignore
        fast = fast.next.next  # type: ignore
    return slow.val if slow else None

print(middle(from_list([1, 2, 3, 4, 5])))

Key takeaways

• One pass, O(1) extra space.
• For two middles in even lists, pick the second with while fast and fast.next as written.
• Different templates pick the first middle—state your rule.