重排链表

题号：NC106
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

将给定的单链表 $\ L$ ： $L_0→L_1→…→L_{n-1}→L_ n$
重新排序为： $L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…$
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

数据范围：链表长度 $0 \le n \le 20000$ ，链表中每个节点的值满足 $0 \le val \le 1000$

要求：空间复杂度 $O(n)$ 并在链表上进行操作而不新建链表，时间复杂度 $O(n)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

复制

{1,2,3,4}

返回值

复制

{1,4,2,3}

说明

给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 1

示例2

输入

复制

{1,2,3,4,5}

返回值

复制

{1,5,2,4,3}

说明

给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出

示例3

输入

复制

{}

返回值

复制

{}