Reorder List

Q:
Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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}.
A:
就是简单的，递归调用，每次减少2步，然后，把最后一个弄到前面来。
---------------------------可是，当list太长的时候，有run time error???????? 这里，估计是StackOverflowError
调用得太多太长。因此，我们下一步就考虑用循环而不是递归？？？？

public class ReorderList {
    public void reorderList(ListNode head) {
        // use re-cursive call, to update
        // find number of Nodes
        int nNodes = 0;
        ListNode pointer = head;
        while (pointer != null) {
            nNodes++;
            pointer = pointer.next;
        }
        if (nNodes > 2) {
            reorderList(head, nNodes);
        }
    }

    private ListNode reorderList(ListNode head, int nNodes) {
        // return the LastNode of reordered list
        if (nNodes == 1) {
            return head;
        } else if (nNodes == 2) {
            return head.next;
        } else { // nNodes > 2
            ListNode lastOfSub = reorderList(head.next, nNodes - 2);
            // detatch the last node
            ListNode lastNode = lastOfSub.next;
            lastOfSub.next = lastNode.next;
            // insert last node afte head
            lastNode.next = head.next;
            head.next = lastNode;

            return lastOfSub;
        }

    }
}

------------------------------下面的算法，避免了stack over flow error---------------
思想是：既然就是把后半儿插入到前半部分。那么我们只需要取下后半部分，然后把指针逆转，再加入，即可。

public class Solution {
   public void reorderList(ListNode head) {
        // IDEA: we need detach the right half part, and reverse their list
        if (head == null) {
            return;
        }
        // find the middle
        ListNode header1 = new ListNode(0);
        header1.next = head;

        ListNode slow = header1, fast = header1;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode midNode = slow.next;
        slow.next = null;

        // reverse the list pointer
        ListNode header2 = new ListNode(0); // HEADER only
        ListNode tmp;
        while (midNode != null) {
            tmp = midNode;
            midNode = midNode.next;
            tmp.next = header2.next;
            header2.next = tmp;
        }
        // Now add the reversed right half to left half list
        ListNode p1 = header1.next;
        while (header2.next != null) {
            // detach the first of
            tmp = header2.next;
            header2.next = tmp.next;
            
            // insert the detached node  after p1            
            tmp.next = p1.next;
            p1.next = tmp;

            p1 = tmp.next;
        }

    }
}

Mistakes:
1: 方法一，用了O(n) 次调用，效率比较差。
2:  方法2 的时候，开始忘了 加入：

            header2.next = tmp.next;

Learned: