class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
def middle(node: ListNode) -> ListNode:
slow = fast = node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse(node: ListNode) -> ListNode:
pre = None
cur = node
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def interweave(L: ListNode, R: ListNode) -> ListNode:
node = L
while R.next:
L.next, L = R, L.next
R.next, R = L, R.next
return node
return interweave(head, reverse(middle(head)))