算法：99.重排链表

https://www.lintcode.com/problem/reorder-list/description

描述

给定一个单链表L:L→L1→…→Ln-1→Ln,

重新排列后为：L→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的情况下进行原地操作。

样例

给出链表，重新排列后为。

思路

一个简洁的实现，直接的思路，每次查找最后一个节点，插入现在的节点后面。

上面这个实现算是非常简洁了，不过效率较低，每次都要搜索一下最后的节点。

注意边界的处理，对 lastNode 的空值判断。

一个更高效的版本：

在这个实现中，整体分为三部分，第一步，查找链表的中点，第二步，翻转链表的后半部分。第三步，合并两个链表。

节点在处理时一定要注意边界的情形，对next字段也需要仔细处理，防止形成环造成死循环。