Reorder List

The problem. Given the head of a list L0 → L1 → … → Ln-1 → Ln, reorder it in place to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … — first, last, second, second-to-last, and so on. Only the links may change, not the values.

Example

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

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

The function returns nothing — it rearranges the list it was given. The hard part is reaching "the last node" again and again in a list that only walks forwards.