reorder-list（链表重排序）

知识点：链表

题目描述

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

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}.

给定一个链表$ L: L_0→L_1→…→L{n-1}→L_n$, 将其重排序为： $L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…$ 你必须在不改变节点值的情况下完成。比如：给定{1,2,3,4},重排序为：{1,4,2,3}

比如：$ L: L_0→L_1→…→L{n-1}→L_n$，首先利用快慢指针将该链表分为两个部分：

$L_a:L_0→L_1→…L_{\frac{n}{2}}$,

$L_b:L_{\frac{n}{2}+1}→L_{\frac{n}{2}+2}→…L_{n}$

然后将$L_b$翻转，然后合并$L_a$和$L_b$即可。