143. reorder list

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class  {
    // 1. find middle
    //     2. reverse 后一个list
    //     3. 把两个list merge 起来
    public void reorderList(ListNode head) {
       // mid：if even，前一个
        // 第二个list从mid下一个开始
        // find mid
        if (head == null) {
            return;
        }
        ListNode mid = findMid(head);
        ListNode head2 = mid.next;
        mid.next = null;
        // reverse second list
        head2 = reverse(head2);
        // merge
        merge(head, head2);

    }
    private ListNode findMid(ListNode head) {
        // 1 2 3 4 5
        // s s s
        // f   f   f

        // 1 2 3 4 5 6
        // s s s
        // f   f   f
        // for even, fast.next.next != null
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode reverse(ListNode head) {
        // recursion / iterative
        ListNode prev = null; // local variable don't have defalt value
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    private void merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        int index = 0;
        while (head1 != null && head2 != null) {
            if (index % 2 == 0) {
                prev.next = head1;
                head1 = head1.next;
            } else {
                prev.next = head2;
                head2 = head2.next;
            }
            prev = prev.next;
            index++;
        }
        if (head1 != null) {
            prev.next = head1;
        } else {
            prev.next = head2;
        }
        dummy.next = null;

    }
}