Reorder List

# 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 listin-place instead.
        """
        #1 Locate middle
        sp, fp = head, head.next
        while fp and fp.next:
            sp = sp.next
            fp = fp.next.next

        #2 Reverse the second half
        sp.next, pre, curr = None, None, sp.next
        while curr:
            curr.next, curr, pre = pre, curr.next, curr

        #3 Interleave the two separated halfs
        curr1, curr2 = head, pre
        while curr2:
            curr1.next, curr2.next, curr1, curr2 = curr2, curr1.next, curr1.next, curr2.next

        return head