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.