Reorder List

Statement

Given the head of a singly linked list, reorder the list as if it were folded on itself. For example, if the list is represented as follows:

$L_{0}$ → $L_{1}$ → $L_{2}$ → … → $L_{n-2}$ → $L_{n-1}$ → $L_{n}$ ​

This is how you’ll reorder it:

$L_{0}$ → $L_{n}$ → $L_{1}$ → $L_{n - 1}$ → $L_{2}$ → $L_{n - 2}$ → …

You don’t need to modify the values in the list’s nodes; only the links between nodes need to be changed.

Constraints:

• The range of number of nodes in the list is $[1, 500]$.

• $-500 \leq$ Node→value $\leq 500$

Examples