Skip to interview prep
Apexed

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.

Reorder a list L1->L2->...->Ln into L1->Ln->L2->Ln-1->... in place. — Data structures & algorithms interview question — Apexed