Solutions

# Brute force using an array. Or: find the seocnd hald (slow and fast pointers), invert it, and then merge the two halves.
# linked-list,two-pointers


# Two pointers - O(n) time, O(1) space
def reorderList(head: ListNode|None) -> None:
    # Find half with slow and fast pointers
    slow, fast = head, head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    
    # Invert second half
    second = slow.next # the head of the second half
    slow.next = None
    prev = None
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp

    # Loop through first half and reversed second half and latch them together
    first = head
    second = prev # the head of the second half reversed
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

# Brute force - O(n) time, O(n) space
def reorderList(head: ListNode|None) -> None:
    arrlist = []
    cur = head
    while cur != None:
        arrlist.append(cur)
        cur = cur.next

    l, r = 0, len(arrlist)-1
    cur = head
    while l < r:
        arrlist[l].next = arrlist[r]
        l += 1

        if l >= r:
            break

        arrlist[r].next = arrlist[l]
        r -= 1

    arrlist[l].next = None