Reorder List
mediumTime: O(n)Space: O(1)
Recognize the pattern
reorder L0→Ln→L1→Ln-1→...interleave first half with reversed second halfthree-step process
Brute force idea
Convert to array, reorder by index, rebuild — O(n) space.
Better approach
Find middle (slow/fast) → reverse second half → interleave both halves. O(n) time, O(1) space.
Key invariant
The reordered list alternates between first-half (forward) and second-half (reversed). Three operations achieve this without extra space.
Watch out for
Not splitting the list properly — set middle.next = null to disconnect before reversing.