104. Reorder a list L1->L2->...->Ln into L1->Ln->L2->Ln-1->... in place.
MediumLinked lists
Technical
Show model answer
Three steps: find the middle with slow/fast pointers and cut the list there; reverse the second half; then merge the two halves by alternating nodes (take one from the first, one from the reversed second). All steps relink existing nodes.
O(n) time and O(1) extra space. A simpler approach pushes all nodes onto a stack or array and links them from both ends, which is O(n) space. Be careful to terminate the first half with null so the final list does not loop.