Reorder List

https://leetcode.com/problems/reorder-list/

A combination of middle-of-linked-list, reverse-linked-list, and merge-two-sorted-lists.

if not head:
    return
 
# Find middle
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
 
# Reverse
prev, curr = None, slow
while curr:
    curr.next, prev, curr = prev, curr, curr.next
 
# Merge
first, second = head, prev
while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next