# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# slow point to the middle point of the linked list
def reverse(node):
if not node or not node.next:
return node
last = reverse(node.next)
node.next.next = node
node.next = None
return last
r = reverse(slow.next)
slow.next = None
tmp = head
while r:
tmp_next = tmp.next
r_next = r.next
tmp.next = r
r.next = tmp_next
tmp = tmp_next
r = r_next
return head
