You are given the head of a singly linked-list: L₀ → L₁ → … → Lₙ₋₁ → Lₙ. Reorder it to: L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → …. You may not modify the values in the list's nodes — only the nodes themselves may be changed.
[1,2,3,4][1,4,2,3][1,2,3,4,5][1,5,2,4,3]slow.next … end)l1 and l2 by rewiring .next pointersFinding the middle splits the list into two halves of equal (or near-equal) length. Reversing the second half lets us pair elements from both ends simultaneously. The interleave step then weaves them together by advancing one pointer from the front and one from the back, alternating which chain we stitch in each iteration — producing exactly the required ordering without any extra memory.
Putting the nodes in an array and picking from both ends uses O(n) space. We can do it with three in-place steps.
Find the middle with fast and slow pointers, and cut the list there. Reverse the second half. Merge the two halves by taking one node from each, alternately.
Split, reverse, merge. The same building blocks as the palindrome check.
Run the animation above on your own input, or watch the 1:05 video explanation of Reorder List with a dry run and Java code.