1
class Solution:
2
    def reverse(self, head):
3
        prev = None
4
        after = None
5
        curr = head
6
        while curr:
7
            after = curr.next
8
            curr.next = prev
9
            prev = curr
10
            curr = after
11
        return prev
12

13
    def find_middle(self, head):
14
        slow = head
15
        fast = head
16
        while fast and fast.next:
17
            fast = fast.next.next
18
            slow = slow.next
19
        return slow
20

21
    def reorderList(self, head: Optional[ListNode]) -> None:
22
        mid = self.find_middle(head)
23
        rev = self.reverse(mid)
24
        first = head
25
        second = rev
26

27
        while second.next:
28
            temp = first.next
29
            first.next = second
30
            first = temp
31

32
            temp = second.next
33
            second.next = first
34
            second = temp