Reorder List
Medium· fast and slow pointers· reversal
Problem
Rearrange a list L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ..., alternating from the front and back. Change the links in place; do not modify the node values.
Examples
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints
- • 1 <= number of nodes <= 5 * 10^4
- • 1 <= Node.val <= 1000
Hints & approach
Hint 1
The result interleaves the first half with the second half read backwards.
Hint 2
Find the middle, reverse the second half, then weave the two halves.
Approachtry the hints first
This combines three basic moves. First find the middle with slow and fast pointers and cut the list there. Next reverse the second half in place. Finally merge by alternating: take one node from the first half, then one from the reversed second half, until the second half runs out. Every step is linear and uses only a few pointers.
Time O(n) · Space O(1)