Given a singly linked listL: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}.

    private ListNode reverse(ListNode head){
        ListNode prev = null;

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

    private ListNode getMiddle(ListNode head){
        ListNode fast = head.next;  
        ListNode slow = head;

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

    private void merge(ListNode h1, ListNode h2){
        ListNode dummy = new ListNode(0);

        while(h1 != null && h2 != null){
            dummy.next = h1;
            h1 = h1.next;
            dummy = dummy.next;
            dummy.next = h2;
            h2 = h2.next;
            dummy = dummy.next;
        }
        if(h1 != null){
            dummy.next = h1;
        } else if(h2 != null){
            dummy.next = h2;
        }
    }

    public void reorderList(ListNode head) {  

        if(head == null){
            return;
        }
        ListNode middle = getMiddle(head);
        ListNode reverse = reverse(middle.next);
        //important
        middle.next = null;
        merge(head, reverse);

    }