Reorder the list as first, last, second, second last, and so on. Change the links in place, not the values.
DSA Animator › DSA Revision › Linked List › Reorder List
Remember: split, reverse, merge. The same building blocks as the palindrome check. The video solves Reorder List (LeetCode 143, Medium) with the Fast & Slow + Reverse + Merge pattern from the Linked List topic, and you can replay every step in the interactive Reorder List animation.
Reorder the list as first, last, second, second last, and so on. Change the links in place, not the values.
For 1, 2, 3, 4, 5, the result is 1, 5, 2, 4, 3.
Putting the nodes in an array and picking from both ends uses O of 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.
The middle is 3, so the halves are 1, 2, 3 and 4, 5. Reversing the second half gives 5, 4. Weave them: 1, then 5, then 2, then 4. Then 3 stays at the end. The list is 1, 5, 2, 4, 3.
In code, find the middle and cut it with slow dot next equals null. Reverse the second half. Then, while the second half has nodes, link one from the first half, then one from the second. It's O of n time and O of 1 space.
Remember: split, reverse, merge. The same building blocks as the palindrome check.