Given a linked list with nodes x0 -> x1 -> ... -> x(n-1), rearrange it in place into
x0 -> x(n-1) -> x1 -> x(n-2) -> x2 -> x(n-3) -> ...
(first, last, second, second-to-last, and so on). Write reorder_list(head); it returns None and must re-link the existing nodes rather than change their values or create new ones.
a -> b -> c -> d becomes a -> d -> b -> c
a -> b -> c -> d -> e becomes a -> e -> b -> d -> c
Lists can have 200,000 nodes, so walking to the tail over and over (O(n²)) is too slow. Aim for O(n) time and, ideally, O(1) extra memory. (Copying the nodes into a Python list is also O(n) and allowed, but try the pointer-only version.)
Show hint
Split the job into smaller linked-list drills you already know: find the middle, deal with the second half so you can walk it from the tail end, then combine the two halves.