LeetCode 143 Reorder List - Example and Complexity Analysis

Trace 1 → 2 → 3 → 4 → 5.

Step 1: Find middle. Slow/fast pointers. When fast reaches the end, slow is at 3. Split into 1 → 2 → 3 and 4 → 5.

Step 2: Reverse second half. 4 → 5 becomes 5 → 4.

Step 3: Merge alternating.

• Take 1, then 5: 1 → 5
• Take 2, then 4: 1 → 5 → 2 → 4
• Take 3: 1 → 5 → 2 → 4 → 3

Result: 1 → 5 → 2 → 4 → 3.

Each step traverses the list once. $O(n)$ time total. Only pointer variables used. $O(1)$ space.