Reorder List

mediumLinked Listfind middle + reverse second half + interleave mergeB75Solve on LeetCode#143

Given the head of a singly linked list L0 -> L1 -> ... -> Ln, rearrange its nodes in place into the order L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... — alternating between the front and the back of the original list.

You must move the actual nodes, not just rewrite their values. The list has between 1 and 5 * 10^4 nodes, so the solution should be O(n) time with O(1) extra space.

Examples

Input:: head = [1, 2, 3, 4]
Output:: [1, 4, 2, 3]

First from the front (1), first from the back (4), second from the front (2), second from the back (3).

Input:: head = [1, 2, 3, 4, 5]
Output:: [1, 5, 2, 4, 3]

The middle node 3 lands at the end when the length is odd.

Hints

One at a time — struggle first, peek second.

Your thinking space — verify on LeetCode, then mark it.