Reorder List

def reorderList(head):
    slow = fast = head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    prev, cur = None, slow.next
    slow.next = None             # cut
    while cur:
        nxt = cur.next
        cur.next = prev          # flip
        prev, cur = cur, nxt
    first, second = head, prev
    while second:
        n1, n2 = first.next, second.next
        first.next = second
        second.next = n1
        first, second = n1, n2

Reorder List. Picture a linked list as a line of circus elephants, each holding the next one's tail. Reorder it in place: first, last, second, second to last, and so on, until the ends meet in the middle.

One, two, three, four becomes one, four, two, three. One through five becomes one, five, two, four, three. Only the links may change, not the numbers.

The easy way copies the nodes into an array and relinks them from both ends, but that costs order n extra space. Walking to the tail for every link instead costs order n squared time.

The trick is three steps. Find the middle: slow moves one step while fast moves two, so when fast hits the end, slow is in the middle. Reverse the back half. Then merge the halves, taking one from each in turn.

In code, slow and fast walk until fast runs out. Cut after slow, and flip each link of the back half. Then, while the back half has nodes, point first at second, point second at first's old next, and step both forward.

Try one through five. Slow goes to two as fast goes to three, then slow goes to three as fast reaches five, the end. So three is the middle. Cut after three, and four, five turns around into five, four. Merge: one takes five, five takes two, two takes four, four takes three.

Each step is a single pass, so it's order n time, and only a few pointers move, so it's order one space.

Middle, reverse, merge. That's Reorder List.