算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
## Reorder List


### 描述

Given a singly linked list $$L: L_0 \rightarrow L_1 \rightarrow \cdots \rightarrow L_{n-1} \rightarrow L_n$$,
reorder it to: $$L_0 \rightarrow L_n \rightarrow L_1 \rightarrow L_{n-1} \rightarrow L_2 \rightarrow L_{n-2} \rightarrow \cdots$$

You must do this in-place without altering the nodes' values.

For example,
Given `{1,2,3,4}`, reorder it to `{1,4,2,3}`.


### 分析

题目规定要in-place,也就是说只能使用`O(1)`的空间。

可以找到中间节点,断开,把后半截单链表reverse一下,再合并两个单链表。


### 代码

{% codesnippet "./code/reorder-list."+book.suffix, language=book.suffix %}{% endcodesnippet %}