def reorder_list(head: ListNode | None) -> None:
    if not head:
        return

    # step 1: find middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # step 2: reverse second half
    second = slow.next
    slow.next = None
    prev = None
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp

    # step 3: merge two halves
    first, second = head, prev
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

# Time: O(n), Space: O(1)

Linked Lists — Reversal, Cycle Detection

Linked Lists — Reversal, Cycle Detection

Linked Lists — Reversal, Cycle Detection