Reorder List

Problem

You are given the head of a singly linked list n0 -> n1 -> n2 -> ... -> n(k-1). Rearrange the nodes in place so that they alternate between the front and the back: n0 -> n(k-1) -> n1 -> n(k-2) -> n2 -> n(k-3) -> .... Only next pointers may be changed; do not modify node values and do not allocate new nodes. The function returns nothing; it mutates the list.

• The list has between 1 and 80,000 nodes.
• Node values fit in a signed 32-bit integer.

Examples

• 3 -> 8 -> 12 -> 20 → 3 -> 20 -> 8 -> 12. Front, back, second, second-to-last.
• 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 → 10 -> 70 -> 20 -> 60 -> 30 -> 50 -> 40. With an odd count, the middle element ends up last.
• 9 → 9. A single node is unchanged.

Hints

1. The result interleaves the first half (in order) with the second half (in reverse). Can you build those two halves without extra memory?
2. Finding the middle of a singly linked list in one pass is a two-speed-pointer job, and reversing a list in place is a standard routine.
3. Split at the middle, reverse the second half, then merge the two halves alternately.