143：重排序链表

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

一共分为3步：
    1、找到链表的中间节点
    2、从中间节点之后断开链表，并反转后半部分链表
    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) return;
        ListNode fast=head;
        ListNode slow=head;

        ListNode l2=head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }

        ListNode head1=slow.next;
        ListNode pre=null;
        slow.next=null;
        while(head1!=null){
            ListNode next=head1.next;
            head1.next=pre;
            pre=head1;
            head1=next;
        }


        ListNode cur=pre;
        while(cur!=null){
            ListNode next1=l2.next;
            ListNode next2=cur.next;
            l2.next=cur;
            cur.next=next1;
            l2=next1;
            cur=next2;
        }
    }
}