链表重排序.md

reorder-list（链表重排序）

知识点：链表

题目描述

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

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\to L_n\to L_1\to L_{n-1}\to L_2\to L_{n-2}\to \dots$ 你必须在不改变节点值的情况下完成。 比如： 给定{1,2,3,4},重排序为：{1,4,2,3}

解题思路

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

$L_a:L_0\to L_1\to \dots L_{\frac{n}{2}}$,

$L_b:L_{\frac{n}{2}+1}\to L_{\frac{n}{2}+2}\to \dots L_n$

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

代码

这里