Reorder List
Reorder List is a medium Linked List problem from the Blind 75. The key pattern is middle + reverse + weave, and a good solution runs in O(n) time.
Problem
Reorder L0,L1,...,Ln as L0,Ln,L1,Ln-1,... and return the resulting value array.
Examples
Example 1
Input
[1,2,3,4,5,6]Output
[1,6,2,5,3,4]Example 2
Input
[1,2,3,4]Output
[1,4,2,3]Example 3
Input
[1]Output
[1]Approach
Find the middle with a slow and a fast pointer, reverse the second half, then alternate nodes from the two halves.
| Pattern | Middle + reverse + weave |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
Cut the list at the middle before weaving, or the result loops.