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. head may be None (an empty list); then do nothing.
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. ⭐ Bonus: walking to the tail over and over (O(n²)) still passes; a speed test earns a star in O(n) time. Ideally use O(1) extra memory too. (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.