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)))