Reorder List

For the required order L0 -> Ln -> L1 -> Ln-1 ..., first find the midpoint using slow and fast pointers. When fast reaches the end, slow is at the end of the first half for the usual split. Save slow.next, set slow.next = null, and reverse that second half iteratively. Then weave the two lists: save firstNext and secondNext, attach first.next = second, attach second.next = firstNext, and advance both saved pointers. Stop when the reversed second half is exhausted.

Splitting before weaving is essential: otherwise the old links can form a cycle or cause nodes to be repeated. The invariant during merge is that the prefix already built follows the desired alternating order and both saved next pointers still own the unmerged suffixes. Test empty and single-node lists, two nodes, and odd and even examples such as 1,2,3,4,5 and 1,2,3,4. Finding, reversing, and weaving are each linear, giving O(n) time and O(1) extra space.