Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.
分析：
本题可以参考reverse Linked List II的做法。
这个题，依次从最后将元素放到前面，比如1,2,3,4,5,6,将6插入到1后面，再将5插入到2后面，再将4插入到3后面。但是因为链表无法从后往前遍历，所以想办法4,5,6三个数从前往后遍历插入到前面，也就是说，先将4,5,6变成6,5,4，即1,2,3,6,5,4，这样就可以从3开始，将3后面元素依次插入到前面，也就是从前往后遍历了。将后面一半元素逆序（4,5,6->6,5,4），也就是reverse linked list II的做法，依次将4后面的元素插入到3后面。
这个题还涉及到求中间的元素，也就是这里的3，因为3后面的元素（后半部分）要逆序，这里使用两个指针，一个走两步，一个走一步，走到最后慢指针就是中间元素了（要开始逆序之前的那个元素）。
综上：1，求出中间元素；2、将中间元素后面的元素逆序（旋转）；3、将旋转后的后半部分依次插入到前面相应位置。
求出中间元素时，对于偶数个元素，可能中间元素取前面那个3，也可能取后面那个4。这里取前面那个3，判断准则见代码。
具体细节见代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if(head==null||head.next==null) return ;
ListNode fast=head;
ListNode slow=head;
//1、找链表的中间元素,如1,2,3,4,5,6，找到3.1,2,3,4,5也是找到3.slow指向中间元素3
while(fast.next!=null&&fast.next.next!=null){//如果是找到1,2,3,4,5,6中的4，只要fast.next!=null
fast=fast.next.next;
slow=slow.next;
} //2、将中间元素后面的元素选旋转,1,2,3,4,5,6->1,2,3,6,5,4.将4后面所有元素依次插入到3后面
ListNode mid=slow;
ListNode start=slow.next;
ListNode then=start.next;//需要往前插入的元素
while(then!=null){
//先断开then节点
start.next=then.next;
then.next=mid.next;
mid.next=then;
then=start.next;
} //3、将后半部分元素依次插入到前面
fast=head;
slow=mid.next;
while(fast!=mid){ //中点时就不用动了，因为最后一个已经在中点后面了，在中点时还要做操作就会出现空指针异常
mid.next=slow.next;//断开slow
slow.next=fast.next;
fast.next=slow;
fast=fast.next.next;
slow=mid.next; } }
}