143. Reorder List

分为以下几个步骤，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||head.next==null)return;
        ListNode slow = head ;
        ListNode fast = head;
        while(fast!=null)
        {
            slow=slow.next;
            fast=fast.next==null?null:fast.next.next;
        }
         ListNode p1 =slow ;
         ListNode p2 =slow.next;
         p1.next=null;
        while(p2!=null)
        {
            ListNode temp =p2.next;
            p2.next=p1;
            p1=p2;
            p2=temp;
        }
        ListNode pos = head ;
        while(p1!=null)
        {
            ListNode res1 = p1.next;
            ListNode res2 = pos.next;
            pos.next= p1;
            p1.next=res2;
            p1=res1;
            pos=res2;
        }
        pos.next=null;
    }
}