reorder-list

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

You are given the head of a singly linked-list. The list can be represented as:

<pre>
L0 &rarr; L1 &rarr; &hellip; &rarr; Ln - 1 &rarr; Ln
</pre>

Reorder the list to be on the following form:

<pre>
L0 &rarr; Ln &rarr; L1 &rarr; Ln - 1 &rarr; L2 &rarr; Ln - 2 &rarr; &hellip;
</pre>

You may not modify the values in the list&#39;s nodes. Only nodes themselves may be changed.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg" style="width: 422px; height: 222px;" />
<pre>
Input: head = [1,2,3,4]
Output: [1,4,2,3]
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg" style="width: 542px; height: 222px;" />
<pre>
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the list is in the range <code>[1, 5 * 104]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 1000</code></li>
</ul>