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.

1，找中点

2，后半段反转

3，前后合并

class Solution {
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;

        while(head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }

    private ListNode mergeList(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        int index = 0;
        while(head1 != null && head2 != null) {
            if(index % 2 == 0) {
                head.next = head1;
                head1 = head1.next;
            } else {
                head.next = head2;
                head2 = head2.next;
            }
            head = head.next;
            index++;
        }
        if(head1 != null) head.next = head1;
        if(head2 != null) head.next = head2;
        return dummy.next;
    }

    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        ListNode mid = findMiddle(head);
        ListNode secondHalf = reverseList(mid.next);
        mid.next = null;
        mergeList(head, secondHalf);    
    }
}