Reorder List

Problem Reorder L0→L1→…→Ln in place to L0→Ln→L1→Ln−1→… — values may not be modified, only node links.

Input / Output

• Input: head of singly linked list. Output: list reordered in place.

Constraints

• Up to 5*10^4 nodes; O(n) time, O(1) space — the array-of-nodes shortcut is O(n) space.

Example

• 1→2→3→4 → 1→4→2→3; 1→2→3→4→5 → 1→5→2→4→3.

Expected approach

• Three sub-routines composed: (1) fast/slow to find the middle and split; (2) reverse the second half; (3) merge the two halves alternately. Each is a standard primitive — the question tests composing them without pointer bugs (terminate the first half, handle odd/even lengths). O(n)/O(1).