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

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Try it yourself

Implement your solution in the following coding playground.