public void reorderList(ListNode head) {
        //find mid
        if (head == null || head.next == null) {
            return;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        ListNode midPre = head;
        while (p1.next != null && (p2.next != null && p2.next.next != null)) {
            p1 = p1.next;
            midPre = p1;
            p2 = p2.next.next;

        }
        //reverse mid -> end
        p1 = p1.next;
        ListNode cur = p1.next;

        midPre.next = null;
        p1.next = null;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = p1;
            p1 = cur;
            cur = t;
        }
        //now p1 is the head, do merge
        ListNode p = head;
        while (p != null && p1 != null) {
            ListNode A = p.next;
            ListNode B = p1.next;
            p.next = p1;
            p1.next = A;
            p = A;
            p1 = B;
        }


    }