"""
You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]


Constraints:
The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000
"""

# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class ReorderList:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return []
        mid = self.findMid(head)
        second_half_head = mid.next
        mid.next = None
        reversed_second_half_head = self.reverse(second_half_head)
        a, b, post_a, post_b = head, reversed_second_half_head, None, None
        while b and a != b:
            post_a = a.next
            post_b = b.next
            a.next = b
            b.next = post_a
            a = post_a
            b = post_b

    def findMid(self, head):
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse(self, head):
        dummy, post = ListNode(0), None
        while head:
            post = head.next
            head.next = dummy.next
            dummy.next = head
            head = post
        return dummy.next
