Data Structures19 sections · 729 units
Open in Course

Problem - Reorder List

Combine multiple techniques

Given a list L0→L1→...→Ln−1→LnL_0 \to L_1 \to ... \to L_{n-1} \to L_n, reorder it to L0→Ln→L1→Ln−1→L2→Ln−2→...L_0 \to L_n \to L_1 \to L_{n-1} \to L_2 \to L_{n-2} \to ... Example: 1→2→3→41 \to 2 \to 3 \to 4 becomes 1→4→2→31 \to 4 \to 2 \to 3. This problem combines three techniques you've learned:

1.1. Find the middle of the list

2.2. Reverse the second half

3.3. Merge the two halves alternately It's a great test of whether you can combine basic building blocks. Constraints: up to 5⋅1045 \cdot 10^4 nodes, values from 11 to 10001000.